Amortised Analysis
Some operations are occasionally expensive and usually cheap, so the worst case of one call overstates the cost of a run of calls. Amortised analysis charges the rare expensive step to the many cheap ones and reports the average per operation over any sequence.
What a learner can do afterwards
- Show that a dynamic array that doubles on overflow appends in constant amortised time
- Use the accounting method to place a credit on each cheap operation
- Explain why an amortised bound is a worst-case claim, not an average-case one
1 · Read
Some operations are usually cheap and rarely costly. Judging them by the rare splurge alone overstates a long run. Amortised analysis spreads the rare costly steps across the many cheap ones and reports the average per operation over any sequence.
Appending to a doubling array usually writes one slot. When the array fills, the next append copies all past items into a doubled home. A million appends still cost only a few million steps, not a million squared, since copies thin out as the array grows.
The accounting trick makes this exact. Each append pays three coins: one spends on the write, two sit as credit on the new slot. A resize that copies k items spends the k stored credits, so the run is prepaid.
An amortised bound is a worst-case promise over the whole run, not an average over random inputs. It holds for any nasty sequence you feed it.
Prepay rare copies with credits from cheap writes, and the average stays constant.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.