Averaging over a sequence
Some operations are usually cheap but occasionally costly, like appending to a dynamic array that sometimes resizes. Amortized analysis asks for the average cost per operation over a whole sequence, which can be far better than the worst single operation suggests.
Charging and saving credit
The accounting method assigns each operation an amortized charge that may differ from its real cost:
- When the charge exceeds the real cost, the surplus is stored as credit on the data structure.
- When the real cost exceeds the charge, stored credit pays the difference.
- The rule for valid charges is that credit must never go negative.
If you can pick charges that keep credit non negative for every sequence, then the total of the charges upper bounds the total real cost.
A concrete picture
For a growing array, charge a small constant per insert. Most inserts cost little and bank credit. When a resize copies many elements, the banked credit exactly covers the copying. Because the saved credit always suffices, the amortized cost per insert stays a small constant even though one operation occasionally does a lot of work.
Key idea
The accounting method overcharges cheap operations to bank credit, so rare expensive operations are prepaid and credit never goes negative.