Coding Interview: Patterns & DSA · Complexity & Big-O · Lesson 2 of 2
Common complexities & amortized cost
You should recognize the standard complexity classes instantly and know which algorithms produce them. Ordered from best to worst for large n:
O(1)constant — hash lookup, array index, stack push.O(log n)logarithmic — binary search, balanced-tree operations.O(n)linear — a single pass over the input.O(n log n)— efficient sorting (merge/heap sort), and many divide-and-conquer solutions.O(n^2)quadratic — nested loops over the same input (naive pair checks).O(2^n)/O(n!)— exhaustive subsets or permutations (backtracking without pruning).
n log n is the sorting wallComparison sorting cannot beat
O(n log n). If your solution starts by sorting, n log n is your floor — so a hash-based O(n) approach, when it exists, is a real win worth naming.Amortized complexity is the average cost per operation across a sequence, even when a single operation is occasionally expensive. A dynamic array append is amortized O(1): most appends are cheap, and the rare doubling-and-copy (O(n)) is spread across the n cheap ones before it.
Worst-case vs amortized vs averageThese are different questions. A hash lookup is O(1) average but O(n) worst case (all keys collide). Say which one you mean — a good interviewer will probe the difference.
◆ Lock it in
- Memorize the ladder:
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n). n log nis the comparison-sort floor — beating it usually means hashing or counting.- Amortized spreads rare expensive ops over many cheap ones (dynamic-array append).
Feynman drill — say it out loudExplain why appending to a dynamic array is amortized O(1) even though a resize copies every element.
Step 1 rate your confidence · Step 2 pick your answer
Which statement about hash-map lookup complexity is most precise?
Step 1 — how sure are you?