Big O
Complexity classes, common data-structure operations, and standard algorithms — all in one reference.
Complexity classes
The operation takes the same time whether the input is 10 or 10 billion. Look for direct lookups: array index, hashmap get/put (average), stack push/pop.
Each step halves the remaining work. Recognized in divide-and-conquer over a structure that supports cheap halving.
Touch every element once. The bread-and-butter complexity for a single pass.
When the work scales with two separate inputs. Common in graph traversal (V + E) and merging two streams.
The lower bound for comparison-based sorting. Appears whenever you sort, build a heap iteratively, or do log-n work n times.
Touching every cell of a 2D grid or doing m work per element in an n-length list. Distinct from O(n+m) — this scales with the product.
Nested loops over the same input. Acceptable for small n (n < ~10k), dangerous beyond that.
Three nested loops. Useful for graph algorithms over small vertex counts.
Generating all subsets, or unmemoized branching recursion. Becomes infeasible past n ≈ 25-30.
All permutations. Infeasible past n ≈ 10-12. Always look for a smarter approach.
Data structure operations
| Structure | Access | Search | Insert | Remove |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Dynamic array Push is O(1) amortized; arbitrary insert/remove shifts elements. | O(1) | O(n) | O(1) amortized | O(n) |
| Linked list (doubly) * given a node reference; locating the node is O(n). | O(n) | O(n) | O(1)* | O(1)* |
| Hash map | — | O(1) avg / O(n) worst | O(1) avg | O(1) avg |
| Balanced BST | O(log n) | O(log n) | O(log n) | O(log n) |
| Binary heap | O(1) for min/max | O(n) | O(log n) | O(log n) |
| Trie L = key length. | O(L) | O(L) | O(L) | O(L) |
| Union-Find (DSU) With path compression + union by rank. α is the inverse Ackermann. | — | O(α(n)) ≈ O(1) | O(α(n)) ≈ O(1) | — |
Canonical algorithms
| Algorithm | Time | Space |
|---|---|---|
| Binary search | O(log n) | O(1) |
| Merge sort | O(n log n) | O(n) |
| Quicksort (avg / worst) | O(n log n) / O(n²) | O(log n) |
| Heapsort | O(n log n) | O(1) |
| Counting sort | O(n + k) | O(k) |
| BFS / DFS on a graph | O(V + E) | O(V) |
| Dijkstra (binary heap) | O((V + E) log V) | O(V) |
| Bellman-Ford | O(V · E) | O(V) |
| Topological sort (Kahn) | O(V + E) | O(V) |
| Kruskal's MST | O(E log E) | O(V) |
| Floyd-Warshall | O(V³) | O(V²) |
| KMP / Z-algorithm | O(n + m) | O(n + m) |
Things that trip people up
Hashmap operations are O(1) average but O(n) worst case (collision chain). Quicksort is O(n log n) average, O(n²) worst. Default to the average case unless the interviewer probes pathological inputs.
Dynamic-array push is O(1) amortized: most pushes are O(1), but an occasional resize is O(n). Averaged over many pushes the cost stays constant. Same idea applies to union-find's α(n) and to most sliding-window inner loops.
Use the right symbol for the right dimension. A heap of size k gives O(log k) ops, not O(log n). Trie ops are O(L) where L is the key length, not the alphabet or the trie size. Mixing them up is a senior interview tell.
O(log₂ n) = O(log₁₀ n) = O(ln n). Constant factors fall out of Big O. Don't fixate on the base — just say "log n."