Complexity Analysis
Complexity analysis predicts how running time and memory grow with input size. Interviewers expect you to derive it from the code — loops, recursion and hidden library costs — not to recite it.
Key points
- 1
O is an upper bound, Ω a lower bound and Θ a tight bound. Best, average and worst case are separate functions, and each can be bounded with any of the three.
- 2
Drop constants and lower-order terms: 3n² + 10n + 7 is Θ(n²). Nested independent loops multiply, sequential loops add, and halving or doubling loops are logarithmic.
- 3
For recursion, write the recurrence. T(n) = 2T(n/2) + n is n log n, T(n) = T(n/2) + 1 is log n, T(n) = T(n − 1) + n is n², and T(n) = 2T(n − 1) + 1 is 2ⁿ. Use the master method or a recursion tree.
- 4
Space includes the call stack: recursion n deep uses O(n) space even if it allocates nothing else.
- 5
Amortized analysis bounds a whole sequence of operations. Doubling dynamic arrays give O(1) amortized appends even though a single resize costs O(n); fixed-size growth gives O(n).
- 6
Know Python's hidden costs: slicing and
list + listcopy,x in listis linear,list.insert(0, x)is linear, dict and set lookups are O(1) on average but O(n) in the worst case. - 7
Sanity-check feasibility from the constraints: about 10⁸ simple operations per second means n = 10⁵ needs roughly O(n log n), and n = 20 allows O(2ⁿ).
Common traps
Calling a loop O(n²) just because it is nested: if the inner pointer never resets (two pointers or sliding window), the total is O(n).
Saying naive Fibonacci is Θ(2ⁿ): 2ⁿ is only an upper bound, and the tight bound is Θ(φⁿ).
Forgetting that a recursive slice such as
f(a[1:])turns an O(n) recursion into O(n²) time and memory.
Read the source
Test yourself on Complexity Analysis
Ten questions, with the answer and explanation after each one.