Averaging over a sequence
Worst case analysis of a single operation can be misleading. A dynamic array that doubles when full has one costly resize, yet most insertions are trivial. Amortized analysis measures the average cost per operation over a whole sequence, giving a fairer picture.
The dynamic array example
Appending to a growable array is usually constant time. When the array fills, it allocates a larger block and copies every element, which is expensive.
- Doubling means resizes happen rarely and the copying cost is spread thinly across the many cheap appends that follow.
- The average cost per append stays constant even though individual appends sometimes spike.
Three accounting methods
- The aggregate method totals the cost of a sequence and divides by the number of operations.
- The accounting method charges cheap operations a little extra and banks it as credit to pay for rare expensive ones.
- The potential method tracks a stored potential that rises during cheap steps and falls when expensive work is done.
Amortized is not average case
Amortized cost is a worst case guarantee over a sequence, not a probabilistic average, so it holds even for adversarial inputs.
Key idea
Amortized analysis spreads the cost of rare expensive operations across many cheap ones, giving a per operation bound that holds over any sequence, unlike a probabilistic average.