← All Posts
Complexity Patterns
March 2026 · 16 min read
After learning the theory, the practical skill is looking at code and instantly knowing its complexity. This post gives you the patterns.
Loop Patterns
| Pattern | Code Shape | Complexity | Derivation |
|---|
| Single loop | for i = 0 to n | $O(n)$ | $n$ iterations |
| Nested loop (independent) | for i ... for j = 0 to n | $O(n^2)$ | $n \times n$ |
| Nested loop (dependent) | for i ... for j = 0 to i | $O(n^2)$ | $\sum_{i=0}^{n} i = n(n-1)/2$ |
| Triple nested | for i ... for j ... for k | $O(n^3)$ | $n \times n \times n$ |
| Half each time | for i = n; i > 0; i /= 2 | $O(\log n)$ | Halving principle |
| Double each time | for i = 1; i < n; i *= 2 | $O(\log n)$ | Same as halving |
| Outer log, inner n | for i*=2 ... for j=0 to n | $O(n \log n)$ | $\log n \times n$ |
| Harmonic loop | for i=1..n, j+=i | $O(n \log n)$ | $\sum n/i = n H_n$ |
| Two pointers | while l < r ... l++ or r-- | $O(n)$ | Each pointer moves at most $n$ |
| Sliding window | for r; while ... l++ | $O(n)$ | $l$ and $r$ each move $n$ total |
Recursion Patterns
| Pattern | Recurrence | Complexity | Example |
|---|
| Linear recursion | $T(n) = T(n-1) + O(1)$ | $O(n)$ | Factorial, linked list traversal |
| Linear + work | $T(n) = T(n-1) + O(n)$ | $O(n^2)$ | Selection sort (recursive) |
| Binary recursion | $T(n) = 2T(n/2) + O(1)$ | $O(n)$ | Tree traversal |
| Divide + merge | $T(n) = 2T(n/2) + O(n)$ | $O(n\log n)$ | Merge sort |
| Single branch | $T(n) = T(n/2) + O(1)$ | $O(\log n)$ | Binary search |
| Exponential | $T(n) = 2T(n-1) + O(1)$ | $O(2^n)$ | Fibonacci (naive), power set |
| Reduce by fraction | $T(n) = T(n/2) + O(n)$ | $O(n)$ | Quickselect (average) |
Data Structure Complexity
| Structure | Access | Search | Insert | Delete | Space |
|---|
| Array | $O(1)$ | $O(n)$ | $O(n)$ | $O(n)$ | $O(n)$ |
| Sorted array | $O(1)$ | $O(\log n)$ | $O(n)$ | $O(n)$ | $O(n)$ |
| Linked list | $O(n)$ | $O(n)$ | $O(1)$ | $O(1)$ | $O(n)$ |
| Hash table | - | $O(1)^*$ | $O(1)^*$ | $O(1)^*$ | $O(n)$ |
| BST (balanced) | - | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | $O(n)$ |
| Heap | $O(1)^{**}$ | $O(n)$ | $O(\log n)$ | $O(\log n)$ | $O(n)$ |
| Trie | - | $O(L)$ | $O(L)$ | $O(L)$ | $O(N \cdot L)$ |
* Average case. Worst case is $O(n)$ for hash collisions. ** Min/max only.
Interview Quick-Recognition
| If you see... | Think... | Complexity |
|---|
| "sorted array" + "find" | Binary search | $O(\log n)$ |
| "all pairs" / "every combination" | Nested loops | $O(n^2)$ |
| "all subsets" | Bitmask / power set | $O(2^n)$ |
| "all permutations" | Backtracking | $O(n!)$ |
| "divide in half" | Divide and conquer | $O(n \log n)$ or $O(\log n)$ |
| "sliding window" / "two pointers" | Single pass technique | $O(n)$ |
| "memoization" / "DP table" | Subproblems × transitions | States × cost |
| "BFS/DFS on graph" | Visit all nodes + edges | $O(V + E)$ |
| "heap" / "priority queue" | Insert/extract | $O(\log n)$ per op |
| "sort then process" | Sorting dominates | $O(n \log n)$ + $O(n)$ |
How to Analyze DP Complexity
The time complexity of dynamic programming is:
$$T = (\text{number of states}) \times (\text{cost per state transition})$$
Examples
| Problem | States | Transition | Time | Space |
|---|
| Fibonacci | $n$ | $O(1)$ | $O(n)$ | $O(1)$* |
| 0/1 Knapsack | $n \times W$ | $O(1)$ | $O(nW)$ | $O(W)$* |
| LCS | $n \times m$ | $O(1)$ | $O(nm)$ | $O(m)$* |
| Matrix chain mult. | $O(n^2)$ | $O(n)$ | $O(n^3)$ | $O(n^2)$ |
| TSP (bitmask DP) | $2^n \times n$ | $O(n)$ | $O(n^2 \cdot 2^n)$ | $O(n \cdot 2^n)$ |
* With space optimization (rolling arrays).
Graph Algorithm Complexity
| Algorithm | Time | Space | Notes |
|---|
| BFS / DFS | $O(V + E)$ | $O(V)$ | Queue/stack + visited |
| Dijkstra (with min-heap) | $O((V+E)\log V)$ | $O(V)$ | Priority queue |
| Bellman-Ford | $O(VE)$ | $O(V)$ | Relax all edges $V-1$ times |
| Floyd-Warshall | $O(V^3)$ | $O(V^2)$ | All pairs |
| Topological sort | $O(V + E)$ | $O(V)$ | DFS or Kahn's |
| Kruskal (MST) | $O(E \log E)$ | $O(V)$ | Sort edges + union-find |
| Prim (MST) | $O((V+E)\log V)$ | $O(V)$ | Priority queue |
Common Gotchas
- String operations are not $O(1)$: Concatenation in a loop can be $O(n)$ per operation, leading to $O(n^2)$ total. Use
StringBuilder or reserve.
- Sorting inside a loop: Sorting ($O(n \log n)$) inside an $O(n)$ loop = $O(n^2 \log n)$.
- Hidden copies: Passing a vector by value creates a copy ($O(n)$). Use references.
- Hash collisions: Hash table operations are $O(1)$ average. Worst case is $O(n)$.
- Recursive Fibonacci without memoization: $O(2^n)$, not $O(n)$.
- Amortized vs worst-case:
vector::push_back is $O(1)$ amortized but $O(n)$ worst case for a single call.
Summary
- Loops: Count iterations. Nested = multiply. Log loop = halving. Harmonic = $n H_n$.
- Recursion: Write the recurrence. Apply Master Theorem or recursion tree.
- DP: States × transition cost. Space = states (or optimized with rolling).
- Graphs: Usually $O(V + E)$ for traversal-based algorithms.
- Use the constraint trick: if $n \leq 20$, exponential is fine. If $n \leq 10^5$, you need $O(n \log n)$ or better.