Big-O Cheat Sheet: The Complexity Formulas Every Interview Tests
- O(n log n) is the comparison sort floor — no comparison-based algorithm can beat it for the general case
- Hash map operations are O(1) average but O(n) worst case; state the caveat once and move on
- Build heap is O(n), not O(n log n) — most engineers get this wrong under pressure
- Recursion space is O(call stack depth), not O(total calls); memoized Fibonacci costs O(n) stack and O(n) table simultaneously
- DP time complexity = number of distinct states × work per state, excluding recursive call cost
- Input size thresholds: n ≤ 10^4 allows O(n²); n ≤ 10^5 needs O(n log n) or better; n ≤ 10^7 needs O(n)
- Graph algorithm selection: BFS for unweighted shortest path, Dijkstra for non-negative weights, Bellman-Ford for negative edges
You have 45 minutes, one shot, and an IDE you've never touched before. The absolute worst way to spend those 45 minutes is blanking on whether your nested loop is O(n²) or O(n log n) while your interviewer quietly updates their notes. This cheat sheet has every table, formula, and shortcut you need. Read it the morning of your interview, panic a little less.
The Eight Classes, in Order of Terrifying Growth
The ranking matters more than the formulas. Memorize this:
| Class | Name | Example |
|---|---|---|
| O(1) | Constant | Array index lookup |
| O(log n) | Logarithmic | Binary search |
| O(√n) | Square root | Trial division primality |
| O(n) | Linear | Single loop |
| O(n log n) | Linearithmic | Merge sort |
| O(n²) | Quadratic | Nested loop |
| O(2^n) | Exponential | Subsets enumeration |
| O(n!) | Factorial | Permutations enumeration |
How Fast Do These Actually Blow Up?
| n | O(log n) | O(n) | O(n log n) | O(n²) | O(2^n) |
|---|---|---|---|---|---|
| 10 | 3 | 10 | 33 | 100 | 1,024 |
| 100 | 7 | 100 | 664 | 10,000 | 10^30 |
| 1,000 | 10 | 1,000 | ~10,000 | 10^6 | 10^301 |
| 10,000 | 13 | 10,000 | ~130,000 | 10^8 | dead |
"Dead" is an understatement. At n=10,000, O(2^n) requires more operations than there are atoms in the observable universe. Your laptop would not finish. Your laptop's grandchildren's laptops would not finish. The heat death of the universe would arrive first.
The practical interview threshold: if n can reach 10^5, your solution needs to be O(n log n) or better. Quadratic is fine up to roughly 10^4. Exponential is never fine, but you already knew that.
Data Structure Operations
Arrays and Strings
| Operation | Dynamic Array | Sorted Array |
|---|---|---|
| Access by index | O(1) | O(1) |
| Search by value | O(n) | O(log n) |
| Insert at end | O(1) amortized | O(n) |
| Insert at index | O(n) | O(n) |
| Delete at index | O(n) | O(n) |
| Delete at end | O(1) | O(1) |
String concatenation in a loop is O(n²) in most languages. Strings are immutable, so each + allocates an entirely new copy. Use a list and join(), or a StringBuilder. This bug runs fine on small test inputs and then silently destroys performance in production. It is, right now, happening in codebases you interact with daily.
Hash Map and Hash Set
| Operation | Average | Worst (all collisions) |
|---|---|---|
| Insert | O(1) | O(n) |
| Lookup | O(1) | O(n) |
| Delete | O(1) | O(n) |
The worst case is rare but real. Adversarial inputs can force all keys into the same bucket, collapsing everything to O(n). In interviews, state the average case and note the caveat once. You want to sound precise, not paranoid.
Linked Lists
| Operation | Singly | Doubly |
|---|---|---|
| Access by index | O(n) | O(n) |
| Insert/delete at head | O(1) | O(1) |
| Insert/delete at tail | O(n) | O(1) |
| Insert/delete by pointer | O(1) | O(1) |
| Search | O(n) | O(n) |
If you hold a direct pointer to the node, insertion and deletion are O(1) for doubly linked lists. That is exactly why LRU cache implementations use a doubly linked list. You already have the pointer; you just splice it in or out.
Stacks and Queues
All core operations, push, pop, peek for stacks; enqueue, dequeue for queues, are O(1) when backed by a linked list or circular array. No gotchas here.
Binary Search Tree
| Operation | Average (balanced) | Worst (degenerate) |
|---|---|---|
| Insert | O(log n) | O(n) |
| Search | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Min/Max | O(log n) | O(n) |
"Degenerate" means sorted input turned the tree into a linked list. If you test your BST by inserting [1, 2, 3, 4, 5], congratulations, you just built a linked list with extra steps. AVL trees and red-black trees prevent this by rebalancing after every mutation, guaranteeing O(log n) in all cases.
Heaps (Binary Min/Max Heap)
| Operation | Time |
|---|---|
| Insert | O(log n) |
| Extract min/max | O(log n) |
| Peek min/max | O(1) |
| Build heap from n elements | O(n) |
| Decrease key | O(log n) |
The O(n) build is the one that trips people up. Naively, you'd expect O(n log n) from n inserts. The linear build works because most nodes are near the leaves and do almost no heapify work. If you say "O(n log n) to build a heap" in your interview, the interviewer will correct you, and you will feel it in real time.
Tries
| Operation | Time |
|---|---|
| Insert | O(m) |
| Search | O(m) |
| Prefix search | O(m + k) |
Where m is the key length and k is the number of results returned. Trie operations are independent of n (the total number of stored keys). Adding more words to a trie does not slow down lookups. That is the entire point for autocomplete.
Segment Tree and Fenwick Tree
| Operation | Segment Tree | Fenwick Tree |
|---|---|---|
| Build | O(n) | O(n log n) |
| Range query | O(log n) | O(log n) |
| Point update | O(log n) | O(log n) |
| Range update | O(log n) | O(log n) with trick |
Use a Fenwick tree when you only need prefix sums and point updates. Segment trees handle arbitrary range functions (min, max, GCD) but take more code. If someone asks for range minimum queries in an interview, that is a segment tree.
Sorting Algorithms
| Algorithm | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |
| Radix sort | O(nk) | O(nk) | O(nk) | O(n + k) | Yes |
O(n log n) is the comparison sort floor. Information theory proves it: any comparison-based sort needs at least log₂(n!) comparisons, which is Θ(n log n). You cannot beat it for general sorting, no matter how clever you are. Counting and radix sort sidestep this by not comparing elements at all, but they require integer keys in a bounded range.
Quicksort's O(n²) worst case is triggered by sorted or reverse-sorted input with a naive pivot. Real implementations use random pivots or median-of-three to make this astronomically unlikely. Python's sort() and Java's Arrays.sort() use Timsort: O(n log n) worst case, O(n) on nearly-sorted data.
Graph Algorithms: The Complete Fear Menu
Let V = vertices, E = edges.
| Algorithm | Time | Space | Notes |
|---|---|---|---|
| BFS | O(V + E) | O(V) | Unweighted shortest path |
| DFS | O(V + E) | O(V) | Cycle detection, toposort |
| Dijkstra (binary heap) | O((V + E) log V) | O(V) | Non-negative weights |
| Bellman-Ford | O(VE) | O(V) | Negative weights, detects cycles |
| Floyd-Warshall | O(V³) | O(V²) | All-pairs shortest path |
| Topological sort | O(V + E) | O(V) | DAGs only |
| Kruskal's MST | O(E log E) | O(V) | Sort edges, union-find |
| Prim's MST | O((V + E) log V) | O(V) | Priority queue, dense graphs |
| Tarjan's SCC | O(V + E) | O(V) | Strongly connected components |
For dense graphs (E ≈ V²), Dijkstra with a Fibonacci heap drops to O(E + V log V). Nobody implements Fibonacci heaps in an interview. Binary heap Dijkstra is always the right answer.
Reading Recursive and DP Complexity
Three Tools, In Order
- Recursion tree: draw the tree, multiply (nodes per level) × (work per node) × (levels).
- Recurrence relation + Master Theorem: for divide-and-conquer with constant branching.
- State space × work per state: for DP, top-down or bottom-up.
Master Theorem Quick Reference
For T(n) = a·T(n/b) + O(n^d):
| Condition | Complexity |
|---|---|
| d > log_b(a) (root-heavy) | O(n^d) |
| d = log_b(a) (balanced) | O(n^d · log n) |
| d < log_b(a) (leaf-heavy) | O(n^(log_b a)) |
Examples:
- Merge sort: a=2, b=2, d=1. log₂2=1=d → O(n log n).
- Binary search: a=1, b=2, d=0. log₂1=0=d → O(log n).
- Naive matrix multiply: a=8, b=2, d=2. log₂8=3>2 → O(n³).
DP Complexity Formula
Time = (number of distinct states) × (work done per state, excluding recursive calls)
Space = (memo table size) + (maximum call stack depth)
| Problem | States | Work/state | Time | Space |
|---|---|---|---|---|
| Fibonacci | n | O(1) | O(n) | O(n) table, O(n) stack |
| Coin change | amount × k | O(k) counted in states | O(amount × k) | O(amount) |
| LCS | m × n | O(1) | O(mn) | O(mn), reducible to O(min(m,n)) |
| 0/1 Knapsack | n × W | O(1) | O(nW) | O(W) with rolling array |
| Grid paths | m × n | O(1) | O(mn) | O(n) |
Backtracking Complexity
| Problem type | Time | Space |
|---|---|---|
| All subsets | O(n · 2^n) | O(n) |
| All permutations | O(n · n!) | O(n) |
| All combinations of k | O(k · C(n,k)) | O(k) |
The "n ×" factor comes from copying the result at each leaf. Build output incrementally and you avoid the per-leaf copy cost, though the output still has that many elements regardless, so the total work doesn't disappear.
Space Complexity: The Part Everyone Forgets
- Iterative algorithm: O(1) extra space unless you're building an explicit data structure.
- Recursion: O(depth of call stack). Depth = the longest path to a base case, not the total number of calls.
- BFS: O(V) for the queue, which holds one full level at worst.
- DFS: O(V) for the call stack, which holds one path at a time.
- Memoization: O(states) for the table, plus O(max depth) for the call stack. These are separate costs that coexist simultaneously.
A common interview mistake: saying memoized Fibonacci uses O(n) space and stopping there. The memo table is O(n). The call stack is also O(n). Both exist at the same time. Say "O(n) for the memo table and O(n) for the call stack, O(n) overall" and your interviewer will know you actually thought about it.
You Don't Need to Compute. You Need to Classify.
These heuristics cover 90% of interview situations.
Loop patterns:
- Single loop over n elements → O(n)
- Nested loop, both over n → O(n²)
- Outer loop over n, inner loop halves each time → O(n log n)
- Loop that halves n each iteration → O(log n)
- Two separate loops, not nested → O(n + m), often O(n)
Recursive patterns:
- Calls itself once with n-1 → O(n)
- Calls itself twice with n-1, no memo → O(2^n)
- Calls itself twice with n/2 → O(n) (Master Theorem, leaf-heavy)
- Calls itself twice with n/2, does O(n) work → O(n log n)
Input size to expected complexity:
- n ≤ 20: O(2^n) or O(n!) might pass
- n ≤ 500: O(n²) or O(n² log n) is fine
- n ≤ 10^4: O(n²) borderline, O(n log n) safe
- n ≤ 10^5: O(n log n) or better
- n ≤ 10^7: O(n) required
- n ≤ 10^18: O(log n) or O(1)
Name the right complexity class, confirm it fits the constraint, and move on. That is the whole game.
The Seven Things That Actually Matter
- O(n log n) is the comparison sort floor. You cannot beat it for general sorting.
- Hash map operations are O(1) average, not guaranteed worst case. Say that once.
- Build heap is O(n), not O(n log n). Most people get this wrong.
- Recursion space is O(depth), not O(total calls). Depth is the longest path, not the total nodes visited.
- DP complexity is states × work per state. Count states, then count what happens inside one state.
- Backtracking is O(branches^depth × leaf copy cost).
- For graphs: BFS for unweighted shortest path, Dijkstra for weighted non-negative, Bellman-Ford for negative edges.
The next step after memorizing the tables is being able to explain them clearly under pressure. Try a voice mock at SpaceComplexity before your next interview, you'll get feedback on how well you're communicating complexity analysis, not just whether the number is correct.
Further Reading
- Big-O Notation, Wikipedia
- Master Theorem, Wikipedia
- Time Complexity of Python Built-ins, Python Wiki
- C++ STL Complexity Guarantees, cppreference
- Sorting Algorithm Comparisons, Wikipedia