Time & Space Complexity#
Every FAANG interview expects you to state time and space complexity after coding. This page is the cheat sheet; apply it while reading DSA Patterns solutions.
Big-O rules of thumb#
| Notation | Name | Example |
|---|---|---|
| O(1) | Constant | Hash lookup, stack push |
| O(log n) | Logarithmic | Binary search, balanced BST ops |
| O(n) | Linear | Single scan, BFS/DFS visit each node once |
| O(n log n) | Linearithmic | Merge sort, heap sort, sort + greedy |
| O(n²) | Quadratic | Nested loops, naive two-sum on unsorted array |
| O(2ⁿ) | Exponential | Subsets, brute-force backtracking |
| O(n!) | Factorial | Permutations |
Drop constants and lower terms: O(3n + 5) → O(n).
Different variables stay: O(n + m) for two arrays; O(V + E) for graphs.
Common operation costs#
| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array / list | O(1) | O(n) | O(1)* tail | O(1)* tail |
| Hash map / set | — | O(1)* avg | O(1)* avg | O(1)* avg |
| Binary heap | — | O(n) | O(log n) | O(log n) |
| Balanced BST | O(log n) | O(log n) | O(log n) | O(log n) |
| Linked list | O(n) | O(n) | O(1)* at node | O(1)* at node |
*Amortized or when pointer known. See Data Structures Overview.
Pattern → typical complexity#
| Pattern | Time | Extra space |
|---|---|---|
| Two pointers (sorted) | O(n) | O(1) |
| Sliding window | O(n) | O(1)–O(k) |
| Prefix sum + hash map | O(n) | O(n) |
| Binary search | O(log n) | O(1) |
| Binary search on answer | O(n log R) | O(1) |
| BFS / DFS | O(V + E) | O(V) |
| Dijkstra | O((V+E) log V) | O(V) |
| Union-Find | O(α(n)) per op | O(n) |
| DP (1D table) | O(n) or O(n·W) | O(n) or O(W) |
| Backtracking | O(k·2ⁿ) or O(n!) | O(n) recursion |
| Monotonic stack | O(n) | O(n) |
| Heap top-k | O(n log k) | O(k) |
Amortized analysis#
Dynamic array (Python list.append): Most appends are O(1); occasional resize copies everything → O(1) amortized per append.
When to mention it: "Append is amortized O(1) because resizing is rare" — shows depth in array/list questions.
Master Theorem (divide & conquer)#
For T(n) = a·T(n/b) + O(nᵈ):
| Condition | T(n) |
|---|---|
| d > log_b(a) | O(nᵈ) |
| d = log_b(a) | O(nᵈ log n) |
| d < log_b(a) | O(n^(log_b a)) |
Examples: Merge sort → O(n log n). Binary search → O(log n). See Divide and Conquer.
Space: auxiliary vs total#
- Auxiliary space: Extra memory beyond input (what interviewers usually mean).
- Total space: Input + auxiliary (e.g. output array counts toward total).
Recursion depth adds O(h) stack space (tree height h). Deep skewed tree → O(n) stack — prefer iterative BFS or tail-recursion rewrite when depth matters.
How to analyze your own code#
- Identify the basic operation (comparison, hash lookup, edge relaxation).
- Count how many times it runs as a function of n (loops, recursion tree).
- Account for hidden costs — sorting first, hash building, copying subarrays.
- State space — extra arrays, hash maps, recursion stack, queue size.
Related#
- Recursion — call stack and recurrence
- Sorting — comparison-based lower bound Ω(n log n)
- Greedy vs DP — when polynomial DP beats exponential brute force
- Data Structures Overview — per-structure costs