Foundation · Module 1 · Lesson 4
Amortized analysis
Average cost across a sequence of operations.
Lesson 4 of 123
1d streakDetailed theory
Amortized analysis proves a bound on the average cost per operation over every valid sequence of operations. It allows occasional expensive operations without assuming random inputs.
By the end, you can
- Distinguish amortized cost from average-case and worst-case cost.
- Derive dynamic-array append with aggregate analysis.
- Recognize aggregate, accounting, and potential-method proofs.
Vocabulary
Definitions with concrete meaning
Amortized cost
Total cost of a worst-case operation sequence divided across its operations.
Aggregate method
Bound the total cost T(n) of n operations, then divide by n.
Accounting method
Charge cheap operations extra credits and spend saved credits on later expensive operations.
Potential method
Store prepaid work in a non-negative potential function Φ(state). Amortized cost is actual cost + ΔΦ.
Rules to apply
- 1Amortized does not mean average-case: it needs no probability distribution.
- 2An individual operation can still hit its Θ(n) worst case.
- 3The guarantee applies to the total cost of every valid sequence covered by the proof.
- 4Geometric growth is essential: doubling makes 1 + 2 + 4 + … less than the final scale.
- 5Growing capacity by one each time would copy Θ(n²) elements across n appends.
Worked example 1
Eight appends to a doubling array
Start with capacity 1. Writing a value costs 1; on a full array, copying each old value also costs 1.
append(x):
if size == capacity:
allocate array of capacity * 2
copy size existing values
data[size] = x
size++- 1
List actual costs
Append costs are 1, 2, 3, 1, 5, 1, 1, 1 as capacity grows 1 → 2 → 4 → 8.
- 2
Add writes
Every append writes once, so eight appends contribute 8.
- 3
Add copies
Resizes copy 1 + 2 + 4 = 7 existing values.
- 4
Average the sequence
Total cost is 15, so amortized cost is 15 / 8 < 2 per append.
For n appends, copies form a geometric series smaller than n; total cost is Θ(n), so each append is Θ(1) amortized.
Worked example 2
Why “grow by one” fails
Suppose a full array increases capacity from k to k + 1.
- 1
Count resize copies
Successive expansions copy 1 + 2 + 3 + … + (n−1) values.
- 2
Use the arithmetic sum
The total is n(n−1)/2 = Θ(n²).
- 3
Divide by n appends
Θ(n²) / n = Θ(n) amortized per append.
The growth policy—not merely using an array—creates the constant amortized append guarantee.
Comparison table
Do not mix these guarantees
Each column answers a different performance question.
| Analysis | What is averaged? | Probability needed? | Append example |
|---|---|---|---|
| Worst-case per operation | Nothing | No | Θ(n) for a resizing append |
| Average-case | Random inputs/outcomes | Yes | Depends on a stated distribution |
| Amortized | A sequence of operations | No | Θ(1) per append over any sequence |
| Expected | Algorithmic randomness | Yes | Depends on randomized implementation |
Check your understanding
1Does Θ(1) amortized mean every append takes constant time?
No. A resizing append takes Θ(n); the total across n appends is Θ(n).
2What probability assumption proves dynamic-array append?
None. The aggregate bound holds for every sequence of appends.
3Why does doubling work?
The copied sizes form a geometric series 1 + 2 + 4 + … whose sum is less than twice its largest term.
Cost Model
Complexity & Trade-offs
When to use it
- Dynamic arrays, hash-table resizing, and buffered data structures.
- Stack sequences with multipop and queue implementations using two stacks.
- Any operation sequence with rare rebuilding or cleanup work.
Common mistakes
- Calling amortized analysis “average case.”
- Claiming every operation is constant because the amortized cost is constant.
- Ignoring the resizing policy or failing to bound the complete operation sequence.
Practice prompts
- Compute exact copy counts for 16 appends to a doubling array.
- Compare doubling capacity with growing capacity by one.
- Prove that n stack operations including multipop take O(n) total time.
Mastery check