30-second mental model
- Big-O = how work grows as input
ngrows, ignoring constants. - Drop constants and lower-order terms:
O(3n + 5)->O(n),O(n^2 + n)->O(n^2). - Sequential steps add; nested loops multiply; halving each step is
log n. - Interviews say "Big-O" but almost always mean tight bound (Theta).
Growth classes (fastest -> slowest)
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)
Steps at n = 1,000,000:
| Class | Rough steps | Verdict |
|---|---|---|
O(log n) |
~20 | instant |
O(n) |
10^6 | fine |
O(n log n) |
~2x10^7 | fine |
O(n^2) |
10^12 | too slow |
O(2^n) |
astronomical | only tiny n |
Deriving the answer
Rules of thumb
| Situation | Cost |
|---|---|
| Two separate loops | O(n + m), keep both vars |
| Loop inside a loop | multiply -> O(n*m) |
| Cut the range in half each step | O(log n) |
| Recursion | calls x work-per-call (draw the tree) |
| Loop over shrinking same data (triangle) | O(n^2)/2 = still O(n^2) |
Empirical check (double the input, time it)
2x -> linear · 4x -> quadratic · +constant -> logarithmic.
Data structure op costs (average / worst)
| Structure | Access | Search | Insert/Delete |
|---|---|---|---|
| Array (by index) | O(1) |
O(n) |
end O(1) amort · middle O(n) |
| Dynamic array append | - | - | O(1) amortized (resize O(n) spike) |
| Singly linked list | O(n) |
O(n) |
at known node O(1) |
| Hash table | - | O(1) / O(n) |
O(1) / O(n) |
| Balanced BST (RB/AVL) | - | O(log n) |
O(log n) |
| Binary heap | peek O(1) |
- | push/pop O(log n) |
Heapify a whole array is
O(n), notO(n log n). Unbalanced BST degrades toO(n).
Graph traversal (BFS/DFS)
O(V + E) with adjacency list · O(V^2) with adjacency matrix.
Sorting
| Algorithm | Time | Space | Stable? | Notes |
|---|---|---|---|---|
| Quicksort | O(n log n) avg / O(n^2) worst |
O(log n) |
no | in place, fast in practice |
| Mergesort | O(n log n) always |
O(n) |
yes | |
| Heapsort | O(n log n) |
O(1) |
no | in place |
| Insertion | O(n^2) / O(n) near-sorted |
O(1) |
yes | fastest for tiny n |
| Counting | O(n + k) |
O(k) |
yes | small integer keys only |
| Radix | O(d*(n + k)) |
O(n + k) |
yes | fixed-width keys |
n log nis the comparison-sort floor - you cannot comparison-sort faster. JS/Python use stable Timsort-style hybrids,O(n log n).
Common per-task costs
| Task | Cost / fix |
|---|---|
| String concat in a loop | O(n^2) (immutable) - use a builder/join |
| Membership check | array scan O(n) -> set/hash O(1) |
| Slice/substring | O(k) (the copy) |
| Sort then binary-search | O(n log n) + O(log n) |
| Count pairs, naive | O(n^2) -> hash to O(n) |
| Two-pointer / sliding window | turns O(n^2) scan into O(n) |
Space complexity
- Recursion depth = stack space
O(depth). - Fibonacci: naive recursive
O(2^n)time /O(n)space · memoizedO(n)time · iterativeO(1)space. - Recursion -> explicit stack: stays
O(n)space but avoids stack overflow.
Amortized
Occasional expensive op averaged over a sequence. Dynamic-array append: O(1) amortized, O(n) on the resize.
Amortized
O(1)still hasO(n)spikes - matters on latency-sensitive paths.
Picking a target from n
| Input size | Need |
|---|---|
n <= 10^4 |
O(n^2) fine |
n <= 10^6 |
O(n log n) or better |
n >= 10^8 |
O(n) / O(log n), think streaming / O(1) space |
Read the problem for the intended solution
- "Sorted" -> binary search
O(log n). - "Top k" -> heap
O(n log k). - "Count pairs" -> hash instead of nested loops.
Common pitfalls
- Constants matter: array scan beats linked-list walk (cache locality) at the same
O(n). O(n^2)can beatO(n log n)for tiny n.- Log base never matters - differs by a constant only.
- Hidden costs: a
sort,slice, or spread hiding inside a "single pass" loop. - Hash worst case
O(n): adversarial keys, resize spikes. Load factor typically 0.7-0.75.
Found this useful? Pass it on.