⏱️
Big-O & Complexity
Operation costs, sorting, and how to guess the target complexity from input size.
Guess complexity from n (the single most useful trick)
Given the constraint on n, the intended solution is usually:
| n ≤ | Target complexity |
|---|---|
| 10–12 | O(n!) — permutations / brute force |
| ~20 | O(2ⁿ) — subsets / bitmask DP |
| ~500 | O(n³) |
| ~5,000 | O(n²) |
| ~10⁶ | O(n log n) or O(n) |
| > 10⁶ / 10⁹ | O(log n) or O(1) |
Data structure operations (average)
| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Hash map / set | — | O(1) | O(1) | O(1) |
| Stack / Queue | O(n) | O(n) | O(1) | O(1) |
| Binary heap | O(1) peek | O(n) | O(log n) | O(log n) |
| Balanced BST | O(log n) | O(log n) | O(log n) | O(log n) |
Sorting
| Algorithm | Time | Space | Stable |
|---|---|---|---|
| Quicksort | O(n log n) avg, O(n²) worst | O(log n) | No |
| Mergesort | O(n log n) | O(n) | Yes |
| Heapsort | O(n log n) | O(1) | No |
| Counting / Radix | O(n + k) | O(n + k) | Yes |
Rules of thumb
- Drop constants and lower-order terms: O(2n + 5) → O(n).
- Nested loop over the same n → O(n²); halving each step → O(log n).
- Recursion cost = (number of nodes) × (work per node). Master theorem for divide & conquer.
- Hash map trades O(n) space for O(1) lookup — the classic time/space swap.
SDE-2 Launchpad · Big-O & Complexity cheat sheet