Learn to read complexity
A five-step routine you can run on any solution, and a cheat sheet for what the answers mean.
- 1Find the loops
Ask what each loop's bound depends on. A loop from i to n inside a loop over n is n². A loop whose pointer never resets is usually amortized.
- 2Price the calls
A call inside a loop costs its own complexity. contains on a list, string concatenation and slicing are all linear.
- 3Solve the recursion
Write T(n) in terms of smaller calls. Two calls on n − 1 is 2ⁿ. Two calls on n/2 plus a linear merge is n log n.
- 4Count memory
Separate auxiliary space from the input, and do not forget the recursion stack.
- 5Look for what the inner loop repeats
If it searches or sums something the outer loop could remember, a HashMap or prefix sum can remove it.
| Class | Typical example | Ops at n = 1,000 | Feels like |
|---|---|---|---|
| O(1) | Array index, hash lookup | 1 | Constant |
| O(log n) | Binary search | 10 | Halving each step |
| O(n) | Single loop | 1,000 | Touch each item once |
| O(n log n) | Merge sort, sort then scan | 10,000 | Divide, then linear merge |
| O(n²) | Nested loops over the input | 1,000,000 | Every pair |
| O(2ⁿ) | Naive Fibonacci, subsets | ≈ 10³⁰⁰ | Doubling per element |
Turn on Learning mode in the analyzer to get hints before the answer, or browse the pattern library.