© Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne
Types of analyses
- Best case - Lower bound on cost.
- Worst case - Upper bound on cost.
- Average case - “Expected” cost.
Order-of-growth classifications
| order of growth | name |
|---|---|
| \( 1 \) | constant |
| \( logN \) | logarithmic |
| \( N \) | linear |
| \( NlogN \) | linearithmic |
| \( N^2 \) | quadratic |
| \( N^3 \) | cubic |
| \( 2^n \) | exponential |
notation
| notation | provides | example | used to |
|---|---|---|---|
| Tilde | leading term | \( \sim 10 N^2 \) | provide approximate model |
| Big Theta | asymptotic order of growth | \( \Theta(N^2) \) | classify algorithms |
| Big Oh | \( \Theta(N^2) \) and smaller | \( O(N^2) \) | develop upper bounds |
| Big Omega | \( \Theta(N^2) \) and larger | \( \Omega(N^2) \) | develop lower bounds |
Tilde notation
- Estimate running time (or memory) as a function of input size N
- Ignore lower order terms