Time & Space Complexity Guide
The single most important skill in interviews: given a problem's constraints, instantly know which algorithm class is required — and which will TLE.
1. Input Size → Required Complexity
Modern online judges allow roughly 108 simple operations per second. Use this table to work backwards from constraints to the maximum time complexity your solution can have.
| Constraint (N ≤) | Max Complexity | Typical Algorithms | ~Operations |
|---|---|---|---|
10 | O(N!) | Permutations, brute-force all orderings, generating all permutations | 3,628,800 |
18 | O(2ᴺ · N²) | Bitmask DP with pair states, held-karp TSP variant | ~8.5M |
22 | O(2ᴺ · N) | Bitmask DP, Travelling Salesman Problem (TSP), subset DP | ~92M |
100 | O(N⁴) | 4-nested loops, brute-force on small grids | 100M |
400 | O(N³) | Floyd-Warshall all-pairs shortest path, 3-nested DP, matrix multiply | 64M |
2,000 | O(N² log N) | Sorted DP transitions, segment tree per row, 2D DP with binary search | ~44M |
10,000 | O(N²) | 2-nested loops, bubble/insertion sort, brute-force pair checking | 100M |
100,000 | O(N log N) | Merge sort, heap operations, balanced BST, BIT/Fenwick tree | ~1.7M |
1,000,000 | O(N) | Linear scan, hash map, two pointers, sliding window, prefix sums | 1M |
10⁸ | O(log N) / O(1) | Binary search, math formula, bit tricks, number theory | <30 |
- This is a guide, not a guarantee — constant factors matter. An O(N²) with heavy inner work may TLE at N=5,000.
- When N is not given, assume N ≤ 10⁵ and target O(N log N) or better.
- Memory limit is usually 256MB. An int array of 10⁸ elements ≈ 400MB — will MLE.
- Recursion depth limit: ~10⁴–10⁵ before stack overflow. Use iterative for deeper.
2. Big-O Cheat Sheet — Data Structures
| Data Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Array | O(1) | O(N) | O(N) | O(N) | O(N) |
| Dynamic Array (ArrayList) | O(1) | O(N) | O(1)* | O(N) | O(N) |
| Singly Linked List | O(N) | O(N) | O(1) | O(1)** | O(N) |
| Doubly Linked List | O(N) | O(N) | O(1) | O(1) | O(N) |
| Stack | O(N) | O(N) | O(1) | O(1) | O(N) |
| Queue | O(N) | O(N) | O(1) | O(1) | O(N) |
| Hash Map / Hash Set | N/A | O(1)* | O(1)* | O(1)* | O(N) |
| BST (unbalanced) | O(N) | O(N) | O(N) | O(N) | O(N) |
| BST (balanced — AVL/RB) | O(log N) | O(log N) | O(log N) | O(log N) | O(N) |
| Binary Heap (Min/Max) | O(1)*** | O(N) | O(log N) | O(log N) | O(N) |
| Trie | O(K) | O(K) | O(K) | O(K) | O(N·K) |
| Graph BFS / DFS | — | O(V+E) | — | — | O(V+E) |
* Amortized average. Worst case O(N) due to hash collisions or resizing. ** With reference to node. *** Peek only (top element).
3. Sorting Algorithms Complexity
| Algorithm | Best | Average | Worst | Space | Stable? | Notes |
|---|---|---|---|---|---|---|
| Bubble Sort | O(N) | O(N²) | O(N²) | O(1) | ✅ Yes | Best when nearly sorted |
| Selection Sort | O(N²) | O(N²) | O(N²) | O(1) | ❌ No | Minimum swaps |
| Insertion Sort | O(N) | O(N²) | O(N²) | O(1) | ✅ Yes | Online algorithm, good for small N |
| Merge Sort | O(N log N) | O(N log N) | O(N log N) | O(N) | ✅ Yes | Guaranteed O(N log N), used in Java/Python |
| Quick Sort | O(N log N) | O(N log N) | O(N²) | O(log N) | ❌ No | Usually fastest in practice; worst case with bad pivot |
| Heap Sort | O(N log N) | O(N log N) | O(N log N) | O(1) | ❌ No | In-place, guaranteed O(N log N) |
| Counting Sort | O(N+K) | O(N+K) | O(N+K) | O(K) | ✅ Yes | Only for integers in range [0, K] |
| Radix Sort | O(NK) | O(NK) | O(NK) | O(N+K) | ✅ Yes | K = number of digits; beats comparison sorts for integers |
| Tim Sort | O(N) | O(N log N) | O(N log N) | O(N) | ✅ Yes | Default in Python (sorted()), Java (Arrays.sort for objects) |
- C++
std::sort— IntroSort (QuickSort + HeapSort + InsertionSort hybrid). O(N log N) guaranteed. - Java
Arrays.sort(int[])— Dual-Pivot QuickSort.Arrays.sort(Object[])— TimSort (stable). - Python
sorted() / list.sort()— TimSort. Always stable.
4. Recurrence Relations → Closed Forms
When analyzing recursive algorithms, identify the recurrence and map it to a known closed form using the Master Theorem or pattern matching.
| Recurrence | Closed Form | Example Algorithm | Explanation |
|---|---|---|---|
T(n) = T(n/2) + O(1) | O(log n) | Binary Search | Halve the problem, constant work each step |
T(n) = T(n-1) + O(1) | O(n) | Linear Recursion (factorial) | Reduce by 1, constant work — n steps total |
T(n) = 2T(n/2) + O(n) | O(n log n) | Merge Sort | Split in half, linear merge — log n levels × n work |
T(n) = 2T(n/2) + O(1) | O(n) | Tree Traversal | Visit every node once — n nodes, O(1) per node |
T(n) = T(n-1) + O(n) | O(n²) | Insertion Sort | n + (n-1) + ... + 1 = n(n+1)/2 |
T(n) = 2T(n-1) + O(1) | O(2ⁿ) | Naive Fibonacci / Subsets | Binary tree of depth n → 2ⁿ leaves |
T(n) = T(n/2) + O(n) | O(n) | QuickSelect (avg) | Geometric series: n + n/2 + n/4 + ... = 2n |
T(n) = 3T(n/3) + O(n) | O(n log n) | 3-way Partition Sort | log₃(n) levels, O(n) work per level |
T(n) = T(√n) + O(1) | O(log log n) | Integer Factorization | Iterated square root reduces exponent by half each time |
Master Theorem (quick reference)
For recurrences of the form T(n) = aT(n/b) + f(n) where a ≥ 1, b > 1:
| Condition | Result |
|---|---|
f(n) = O(n^(log_b(a) - ε)) for some ε > 0 | T(n) = Θ(n^log_b(a)) — work dominated by leaves |
f(n) = Θ(n^log_b(a)) | T(n) = Θ(n^log_b(a) · log n) — equal work at each level |
f(n) = Ω(n^(log_b(a) + ε)) for some ε > 0 | T(n) = Θ(f(n)) — work dominated by root |
5. Space Complexity Guide
| Scenario | Space Complexity | Example |
|---|---|---|
| No extra data structures, fixed variables | O(1) | Two-pointer, in-place swap, iterative two-sum |
| Recursion on linear input (no branching) | O(N) — call stack | Iterating linked list recursively, linear DP memo |
| Recursion on tree of depth D | O(D) = O(log N) balanced, O(N) skewed | Tree DFS, balanced BST operations |
| Storing all N elements | O(N) | Hash map/set, prefix sum array, BFS queue |
| 2D DP table | O(N·M) | Edit distance, LCS, 0/1 Knapsack |
| 2D DP with rolling array optimization | O(min(N,M)) | Optimized LCS, knapsack with 1D DP |
| Bitmask DP | O(2ᴺ) | TSP, subset DP, bitmask states |
| BFS on graph | O(V + E) | Level-order traversal, shortest unweighted path |
- Default stack size: ~1MB in most systems → supports ~10,000–50,000 recursive calls
- If N can be 10⁵ and your recursion goes N deep → always use iterative with explicit stack
- Tree DFS on a skewed tree of N=10⁵ nodes → stack overflow. Solution: iterative DFS with stack
- Python's default recursion limit is 1,000. Increase with
sys.setrecursionlimit(10**5)or use iterative.
6. How to Estimate Complexity in an Interview
The 3-Step Method
- Read the constraints. What is N? Is there a second dimension M? What's the time limit?
- Target a complexity class. Use the input→complexity table above to determine the maximum allowed complexity.
- Work backwards to an algorithm. What algorithm class achieves that complexity? Does one exist for this problem type?
Worked Example 1 — Two Sum
Problem: Find two numbers in an array that sum to target. N ≤ 10⁵.
Step 1: N = 10⁵
Step 2: Target O(N) or O(N log N)
Step 3: O(N²) brute force would TLE. O(N) with hash map ✅. Or sort + two pointers = O(N log N) ✅.
Worked Example 2 — Subsets
Problem: Generate all subsets of an array. N ≤ 15.
Step 1: N = 15
Step 2: 2¹⁵ = 32,768 subsets. O(2ᴺ · N) is fine.
Step 3: Backtracking or bitmask enumeration both work. Output itself is O(2ᴺ · N) so we can't do better.
Worked Example 3 — Shortest Path
Problem: Find shortest path in weighted graph. V ≤ 10⁵, E ≤ 2×10⁵.
Step 1: V = 10⁵ (too large for O(V²) Dijkstra)
Step 2: Need O((V + E) log V)
Step 3: Dijkstra with min-heap = O((V + E) log V) ✅. Bellman-Ford = O(V·E) = 2×10¹⁰ ❌ TLE.
"Given N is up to 10⁵, an O(N²) solution would be around 10¹⁰ operations which would TLE. I need O(N log N) or better. I'm thinking of using [algorithm] which would give us O(N log N) time and O(N) space — does that seem reasonable to you?"
Practice These Patterns
Now that you know the required complexity, pick the right pattern to match it:
| Complexity | Go-to Pattern | Practice |
|---|---|---|
O(N) | Two Pointers, Sliding Window, Hash Map | Sliding Window → · Two Pointers → |
O(N log N) | Binary Search, Merge Sort, Heap | Binary Search → |
O(N²) | Dynamic Programming (2D), Backtracking | Dynamic Programming → |
O(V+E) | BFS / DFS on Graphs | Graphs → · BFS → |
O(log N) | Binary Search on Answer | Binary Search → |