Complexity Classes and Recurrences
Common complexity classes
| Class | Name | Growth rate |
|---|---|---|
| O(1) | Constant | Does not grow with input |
| O(log n) | Logarithmic | Grows very slowly |
| O(n) | Linear | Proportional to input |
| O(n log n) | Quasi-linear | Slightly worse than linear |
| O(n²) | Quadratic | Doubling input quadruples cost |
| O(n³) | Cubic | Doubling input multiplies cost by 8 |
| O(2ⁿ) | Exponential | Each additional input element doubles cost |
Logarithms grow very slowly — O(log n) is excellent. Because O notation ignores constant factors, the base of the logarithm is irrelevant.
Growth rate table
How large an input can be processed in a given time:
| Complexity | 1 second | 1 minute | 1 hour | Gain |
|---|---|---|---|---|
| n | 1000 | 60,000 | 3,600,000 | ×60 |
| n log n | 140 | 4,895 | 204,095 | ×41 |
| n² | 31 | 244 | 1,897 | ×8 |
| n³ | 10 | 39 | 153 | ×4 |
| 2ⁿ | 9 | 15 | 21 | +6 |
The “gain” column shows what happens when going from 1 second to 1 minute. For exponential algorithms, the gain is a mere +6 — doubling hardware barely helps.
Exponential vs polynomial
- Polynomial complexity (O(nᶜ)): doubling the input increases cost by a constant factor. Practical for reasonable c, though c > 3 may still be problematic.
- Exponential complexity (O(2ⁿ)): can never handle large inputs, even with huge resources. Already with n = 20 the cost exceeds one million.
Faster hardware does not make good algorithms unnecessary. On the contrary, faster hardware magnifies the superiority of better algorithms: with sillySum (O(2ⁿ)), doubling processing power lets us go from n to n+1; with npower (O(n)), from n to 2n; with power (O(log n)), from n to n².
Simple recurrence relations
| Recurrence | Closed form | Complexity |
|---|---|---|
| T(n+1) = T(n) + 1 | T(n) = n | O(n) |
| T(n+1) = T(n) + n | T(n) = n(n-1)/2 | O(n²) |
| T(n) = T(n/2) + 1 | T(2ⁿ) = n+1 | O(log n) |
| T(n) = 2T(n/2) + n | - | O(n log n) |
These recurrences are read directly from OCaml definitions. The constant work in the recursive step gets unit cost; the base case also gets unit cost. Since we only need an upper bound, these units represent the larger of the actual costs.