DSA & Implementation · intro
Complexity Analysis
Big-O, amortised cost, and space complexity — how to argue a bound before writing code.
Mental model
A complexity bound is a claim about growth, not speed: it says how the work scales as n grows, so constants and hardware drop out. Amortised cost is a separate claim — that an expensive step is rare enough to average down over a sequence, which is why a dynamic array's push is O(1) amortised despite occasionally copying everything. Space is the third axis and the one people forget: recursion depth is memory.
How to study Complexity Analysis
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use MIT 6.006 — Lecture 1: Algorithms and Computation, USACO Guide — Time Complexity, Jeff Erickson, Algorithms — appendix: Solving Recurrences (PDF) to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare Complexity Analysis with Sorting, Binary Search. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Amortised growth of a dynamic array and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Where it matters
Every interview asks for it, and it is the argument you make in a code review when someone adds a nested lookup inside a loop.
Common mistakes
- Reporting the complexity of the loop you can see and missing the one inside the library call (sort, includes, string concat)
- Calling an amortised bound a worst-case bound — a single push can still be O(n)
- Ignoring recursion depth, so an O(n) algorithm quietly uses O(n) stack
- Adding complexities of sequential phases instead of taking the max, or multiplying nested loops that do not actually nest over the same n
Learn from primary sources
Practice and explain it back
Amortised growth of a dynamic array
Implement pushCount(n): build a dynamic array by pushing n items, doubling capacity when full (starting at capacity 1), and return the TOTAL number of element copies performed. This is the sum that makes push O(1) amortised — for n=8 the copies are 1+2+4 = 7.
Expected evidence: pushCount(8) -> 7, pushCount(1) -> 0, pushCount(100) -> 127
Open the interactive drill →Review prompts
- A dynamic array's push is O(1) amortised, yet one push can still take O(n). What does the amortised bound actually promise, and when is it the wrong bound to quote?
Build evidence
Use a roadmap capstone to turn this concept into working evidence.
Prerequisites
None assigned yet.