Big O
Complexity classes, common data structure operations, and standard algorithms 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 standard cost of 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 | n/a | 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. | n/a | O(α(n)) ≈ O(1) | O(α(n)) ≈ O(1) | n/a |
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) |
Common Pitfalls
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 common mistake in senior interviews.
O(log₂ n) = O(log₁₀ n) = O(ln n). Constant factors fall out of Big O, so say “log n” and leave out the base.