Expert · Module 22 · Lesson 1 of 4
Amortized analysis
Some operations are usually cheap and occasionally expensive. Amortized analysis bounds the total cost of any sequence of them, so the average per operation is guaranteed, even though a single operation may be slow.
By the end you can
- Bound the total cost of a sequence of operations with aggregate analysis
- Explain why doubling makes appends O(1) amortized and fixed-size growth makes them O(n)
- Tell amortized cost apart from average-case and expected cost, and know when a worst-case bound is needed instead
Builds on Dynamic arrays and growth, Deques and monotonic stacks.
01 · A question first
Appending to a Python list sometimes copies every element, which is O(n). Yet a loop that appends a million elements runs in linear time, not quadratic. Every textbook calls append O(1) "amortized". What exactly is being promised, and what would break the promise?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Expensive sometimes, cheap on the whole
- Aggregate analysis
- Counting each element's lifetime
- Amortized, average and expected
- When amortized isn't good enough
- A tool for designing, not just analyzing
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Something wrong with this lesson? Report a problem