Amortized Analysis

the potential method

Imagine the data structure has a sort of stored energy that goes up when the structure becomes 'messy' (full array, many 1-bits, an unbalanced tree) and goes down when an operation tidies it. Cheap operations tend to add a little messiness, banking energy; an expensive operation typically releases a lot of that stored energy to pay for its work. The potential method turns this picture into a single function and an exact formula.

You pick a potential function Phi that maps any state of the structure to a number, with Phi never below its starting value (usually Phi >= 0 and Phi(initial) = 0). The amortized cost of an operation is then DEFINED as its actual cost plus the change in potential it causes: amortized = actual + (Phi_after - Phi_before). Now sum over a whole sequence: the potential changes telescope, so the total amortized cost equals the total actual cost plus Phi_final minus Phi_initial. Since Phi_final >= Phi_initial, total amortized cost is at least total actual cost — so summing the amortized costs gives a valid upper bound on the real work. To bound an individual operation you just compute actual + change-in-potential; if a cheap operation raises Phi, its amortized cost is a bit more than its actual; if an expensive operation lowers Phi a lot, the drop cancels most of its actual cost.

The potential method is the most mechanical and most reusable of the three techniques: once you have a good Phi, each operation's amortized cost is a short calculation, and the telescoping guarantees the bound automatically. It is the standard tool for splay trees, Fibonacci heaps, and dynamic arrays. Its difficulty is entirely upfront — finding a potential that makes every operation's amortized cost come out small. The honest caveat: the method never tells you what Phi should be; choosing the potential is the creative, sometimes hard, part.

Binary counter, let Phi = number of 1-bits. An increment that flips t ones to zero and sets one zero to one has actual cost t+1 and changes Phi by (1 - t). Amortized = (t+1) + (1 - t) = 2, regardless of how long the carry chain is. The expensive cascades are exactly the ones that drop Phi a lot, cancelling their cost.

Amortized cost = actual cost + change in potential; summed over a sequence the changes telescope to give a valid total bound.

The telescoping only yields an upper bound because Phi_final >= Phi_initial. If you let Phi dip below its starting value mid-sequence, the bound can break — keep Phi at or above its initial value throughout.

Also called
physicist's methodphysicist method物理學家法勢能法