Collection storing andeque adt
|
|
|
|---|---|---|
|
|
|
| Elena Spasova |
❖ Hint for HW2’s confusingTest(): commenting out resize() is not the answer
2
| CSE373, Winter 2020 |
|---|
easy to be off by one. Will we have to calculate the exact count
at some point?
3
4
| CSE373, Winter 2020 |
|---|
❖ Case Analyses: Best, Worst, Overall
❖ Asymptotic Analysis Case Study: PrintParty
List ADT. A collection storing an
|
|
|---|
| A | B | C |
|---|
7
❖ Asymptotic Analysis Case Study: PrintParty
8
| CSE373, Winter 2020 |
|---|
|
CSE373, Winter 2020 |
|---|
Big-O: Intuition
| CSE373, Winter 2020 |
|---|
❖ … and also …
|
CSE373, Winter 2020 |
|---|
Big-O: Mathematical Definition
12
|
||
|---|---|---|
| Θ(N4) | ||
| Θ(N3) | ||
| NeN+ N | Θ(NeN) | |
| Θ(N2) | ||
13
| Function | Big-Theta | Big-O |
|---|
| CSE373, Winter 2020 |
|---|
means there exist positive
constants k1 and k2 such thatfor all values of N greater than
some N0.
Big-Theta Challenge
means there exist positive constants k1 and k2 such that
Big-Omega: Intuition
❖ Big-Omega is our “greater than or equals”
|
CSE373, Winter 2020 |
|---|
for all values of N greater than
some N0.
N0
Big-O, Big-Theta, Big-Omega Relationship
19
| CSE373, Winter 2020 |
|---|
|
Array contains a |
|
|---|---|---|
| duplicate at front | ||
| ❖ Unless otherwise specified, we | Constant time | Quadratic time |
