The Core Idea
Worst Case Per Operation vs. Average Over a Sequence
Amortized analysis answers a different question than ordinary worst-case analysis. Instead of asking 'what's the worst this single operation could cost?' it asks 'if I perform this operation n times in a row, what's the total cost, divided by n?' Some data structures have operations that are occasionally very expensive, but so rarely expensive that the cost, spread out over many operations, averages down to something small and constant.
This distinction matters because reporting only the worst-case cost of a single operation can make a data structure look far worse than it behaves in practice — a structure with 'O(n) worst case per operation' might actually be extremely efficient if that expensive case is guaranteed to happen only once in a long while.
💡 Memory Trick
Think of a phone contract: most months you pay a flat $30 fee (cheap, routine), but once a year you pay a $360 annual equipment charge (expensive, rare). If someone asks 'what does this phone plan cost per month,' the honest answer isn't 'sometimes $30, sometimes $390' — it's the amortized figure: spread the $360 annual charge over 12 months, and your true average cost per month is $30 + $30 = $60, a smooth, predictable number that accounts for the rare expensive event.
The Classic Example
Dynamic Array (ArrayList / Vector) Doubling
1
The Usual Case: O(1) Append
A dynamic array (like Python's list or Java's ArrayList) has some allocated capacity beyond its current size. Appending a new element when there's still room is simply writing to the next open slot — O(1), instant.
2
The Rare Case: O(n) Resize
When the array is completely full and a new element needs to be appended, the structure must allocate a brand-new, larger block of memory (typically double the old capacity) and copy every existing element into it — an O(n) operation, since all n existing elements must be copied.
3
Why Doubling (Not Adding a Fixed Amount) Is the Key
If capacity grew by resizing to just +1 slot each time it filled up, you'd trigger an O(n) copy on nearly every single append, giving true O(n) cost per operation on average. But because capacity doubles, the expensive O(n) resize happens exponentially less often relative to how many cheap appends occurred since the last resize — specifically, after a resize to size 2k, you get k more cheap O(1) appends before the next resize is needed.
4
The Amortized Result: O(1) Per Append
Summing the total cost of n appends — nearly all O(1), plus O(log n) resize events whose costs are 1, 2, 4, 8, ... up to n — the total work across all n appends comes out to O(n), meaning the amortized cost per individual append is O(n)/n = O(1).
Beyond Dynamic Arrays
Where Else Amortized Analysis Applies
This pattern — cheap operations subsidizing rare expensive ones, provably bounded by design — appears throughout computer science: hash table resizing follows the same doubling logic as dynamic arrays; the union-find (disjoint set) data structure achieves near-constant amortized time per operation through path compression and union by rank; and splay trees achieve amortized O(log n) operations by restructuring the tree on every access, even though a single access can occasionally take longer.
The key giveaway that a problem calls for amortized analysis, rather than simple worst-case analysis, is a data structure whose operations are described as 'usually fast, but occasionally must do a bulk expensive step to maintain its invariants' — the doubling, resizing, or restructuring step is what amortized analysis is built to account for honestly.
🖥️ Applied Scenario
A colleague argues your application's dynamic array-based logging system is inefficient because 'appending has O(n) worst case due to resizing,' and wants to switch to a fixed-size pre-allocated array.
1
You acknowledge that a single append can indeed cost O(n) in the rare case a resize is triggered — your colleague isn't wrong about the worst-case single-operation cost.
2
You explain amortized analysis: because the array doubles in size on each resize, that expensive O(n) event happens exponentially less often as the array grows, and the total cost across any n appends sums to O(n) overall.
3
You calculate that the amortized cost per append is therefore O(n)/n = O(1) — meaning, averaged over a realistic sequence of operations, appends are just as fast as with a fixed-size array.
4
Conclusion: you keep the dynamic array, since a fixed-size array would trade this rare, well-understood resizing cost for a hard capacity limit and no flexibility, without any real average-case performance gain.
📌 Exam Application
Exam questions often ask you to compute the amortized cost of an operation given a described pattern of occasional expensive events (like doubling), typically expecting you to sum total cost across n operations and divide by n. You may also be asked to explain why doubling capacity (rather than adding a fixed increment) is essential to achieving O(1) amortized append — the answer centers on the resize frequency shrinking relative to accumulated cheap operations.
⚠️ Most Common Amortized Analysis Mistakes
The most common mistake is confusing amortized analysis with average-case analysis — they are different concepts. Average-case analysis assumes a probability distribution over possible inputs; amortized analysis makes no assumption about input distribution at all and instead proves a guaranteed bound on the total cost of any sequence of operations, worst input included. Another frequent error is assuming any occasional expensive operation can be 'amortized away' — the doubling (or similarly structured) growth pattern is specifically what makes the math work out to a small constant; a fixed-increment growth strategy would not.
✓ Quick Self-Test
Can you explain, using the numbers, why doubling capacity (rather than adding a fixed number of slots) is what makes dynamic array append achieve O(1) amortized cost? Can you state the difference between amortized analysis and average-case analysis in one sentence?
Next Lesson
Stack vs Queue
→
← All Algorithms Lessons