DSA Visual Mastery
Big-O intuition: the complexity ladder
Big-O is not math homework — it's the language interviewers use to negotiate solutions with you. "Can we do better than O(n²)?" is the most common sentence in coding interviews.
What Big-O actually measures
Big-O answers one question: as the input grows, how fast does the work grow? Constants are ignored because they stop mattering at scale.
The complexity ladder
| Complexity | Name | Typical cause | n = 1,000,000 |
|---|---|---|---|
| O(1) | Constant | Hash lookup, array index | 1 op |
| O(log n) | Logarithmic | Binary search, balanced BST | ~20 ops |
| O(n) | Linear | One pass over input | 10⁶ ops |
| O(n log n) | Linearithmic | Good sorting, heap on all items | ~2×10⁷ ops |
| O(n²) | Quadratic | Nested loops over input | 10¹² ops — too slow |
| O(2ⁿ) | Exponential | Trying all subsets naively | Heat death of universe |
Reading complexity off code — three rules
- 1Sequential steps add — O(n) pass then O(n log n) sort = O(n log n). Keep the biggest term.
- 2Nested loops multiply — a loop inside a loop over the same n = O(n²).
- 3Halving is log — any loop that cuts the problem in half each step runs O(log n) times.
The interview trick: constraints tell you the target complexity
- n ≤ 20 → O(2ⁿ) allowed → backtracking / bitmask
- n ≤ 5,000 → O(n²) fine → nested loops, simple DP
- n ≤ 10⁶ → need O(n log n) or O(n) → sort, heap, hashmap, two pointers
- n ≤ 10⁹ → need O(log n) or O(1) → binary search or math
Before writing any code, look at the constraints. They are the interviewer whispering the intended solution's complexity to you.