Lesson 066
Amortized Analysis
Aggregate · Banker’s · Potential
1:00How to prove that a data structure operation is O(1) on average over a sequence, even when individual operations are occasionally expensive.
By the end, you can
- Define amortized cost and explain why it is a worst-case sequence guarantee rather than an average-case assumption.
- Compute the total write count for n pushes into a doubling dynamic array and derive the amortized cost per push.
- Apply the aggregate method by summing the geometric copy series and dividing by n.
- Apply the accounting (banker's) method by choosing a per-operation charge and verifying the credit balance never goes negative.
- Apply the potential method using Φ = 2·size − capacity to show that the amortized cost of every push (cheap or resize) is the same constant.
- Explain why multiplicative growth achieves amortized O(1) while additive growth does not.
- Describe how hash-table rehashing is amortized O(1) using the same argument.
- Distinguish amortized bounds from average-case bounds and from per-operation worst-case bounds.
Up next in Recursion, Paradigms & Algorithm Analysis
