Complexity classes
| Big O | Name | Typical source | n = 1M feels like |
|---|
| O(1) | constant | hash lookup, array index | instant |
| O(log n) | logarithmic | binary search, heap op, B+tree | ~20 steps |
| O(n) | linear | one pass | milliseconds |
| O(n log n) | linearithmic | good sorting | ~20M steps, fine |
| O(n²) | quadratic | nested loops | 10¹² steps, too slow |
| O(2ⁿ), O(n!) | exponential | subsets, permutations | only for n under ~20 |
Rough guide from input size: n up to 10⁴ allows O(n²). n up to 10⁶ needs O(n log n) or better.
Words interviewers use
| Amortized | Average cost per operation over a long run. A dynamic array push is O(1) amortized even though a resize is O(n). |
| Average vs worst | Hash map O(1) average, O(n) worst. Quick sort n log n average, n² worst. Say both. |
| Space | Extra memory you allocate, plus recursion depth. |
| Stable sort | Equal items keep their original order. |
| In place | O(1) extra memory, apart from recursion. |