Energy in a data structure
The potential method is a powerful way to prove amortized bounds. Instead of tracking credit on individual elements, it defines a single potential function over the whole data structure, a number that measures how much stored up work it holds at any moment.
The amortized cost formula
For each operation, the amortized cost is its real cost plus the change in potential:
- Amortized cost equals real cost plus the new potential minus the old potential.
- When an operation builds up structure, potential rises and its amortized cost exceeds its real cost.
- When an operation does heavy cleanup, potential falls and pays for the real work.
Summing this over a sequence telescopes: the intermediate potentials cancel, leaving the total real cost bounded by the total amortized cost plus the starting potential minus the ending potential.
Making it valid
For the bound to be meaningful you choose a potential that starts at zero and never goes negative, so the final potential cannot secretly hide cost. For a dynamic array you might set the potential to grow with how full the table is, so it peaks right before a resize and drops sharply when the resize spends it. A good potential function turns a messy worst case into a clean constant amortized bound.
Key idea
The potential method bounds amortized cost as real cost plus change in a non negative potential, so summing telescopes into a clean total.