From scattered coins to one number
In the previous guide the accounting method let you overcharge cheap operations and stash the surplus as little coins sitting on individual elements — a coin on each item of a stack, ready to pay for its eventual pop. That works beautifully, but it asks you to track where every coin lives, which gets fiddly once the structure is large or the credits move around. The potential method is the physicist's answer to the same problem: instead of scattering coins across the structure, collapse the entire stored balance into one single number, the potential, written Phi (the Greek letter phi). Phi is a function of the whole data structure's current state, and it stands for "how much prepaid work is banked inside this structure right now."
The analogy that gives the method its name is energy. Lift a weight and you do real work; that work is not lost, it is stored as potential energy in the raised weight, ready to be released later. A data structure operation is the same. Sometimes you do more work than an operation "deserves" and the surplus is stored — Phi goes up. Sometimes you cash that stored work in to pay for an expensive operation — Phi goes down, and its drop helps foot the bill. The genius is that you never have to say which element holds the energy; you only have to assign one honest number to each possible state of the structure.
The one definition that runs everything
Here is the entire machine in one line. Number the states of the structure so D_0 is the starting state and D_i is the state after the i-th operation. Let c_i be the real cost of the i-th operation. Then the amortized cost of that operation is defined to be its real cost plus the change in potential it causes:
amortized cost a_i = c_i + ( Phi(D_i) - Phi(D_{i-1}) )
sum of a_i = sum of c_i + ( Phi(D_n) - Phi(D_0) ) <- telescopes!Now watch why this is worth anything. Add up the amortized costs over a whole sequence of n operations. The potential differences form a telescoping sum: Phi(D_1) - Phi(D_0), then Phi(D_2) - Phi(D_1), then Phi(D_3) - Phi(D_2), and so on. Each Phi in the middle appears once with a plus and once with a minus, so they all cancel in a cascade, leaving only Phi(D_n) - Phi(D_0). That is the whole trick: the sum of amortized costs equals the sum of real costs, plus just the net change in potential from start to finish. If you arrange for the potential to end no lower than it began, the sum of amortized costs is an honest upper bound on the sum of real costs — which is exactly the total running time you wanted to bound.
The two rules that keep you honest
A potential function is not allowed to be anything you like — that would let you prove false bounds by hiding cost in a number that secretly goes negative. Two conditions keep the accounting honest, and they are exactly the conditions that make the telescoping argument deliver a real bound rather than a comforting illusion.
- Start at zero (or set the baseline there): Phi(D_0) = 0. You begin with an empty bank — no prepaid work exists before the first operation. This is just bookkeeping convenience; you can also start higher, as long as you remember to subtract Phi(D_0) at the end.
- Never go into debt: Phi(D_i) >= 0 for every state reached. The bank balance can never be negative, because you cannot spend prepaid work you never deposited. This is the load-bearing condition. If it holds, then Phi(D_n) - Phi(D_0) >= 0, so the sum of real costs is at most the sum of amortized costs — the bound is real.
- Bound each amortized cost: show that a_i = c_i + Phi(D_i) - Phi(D_{i-1}) is small (often O(1) or O(log n)) for EVERY operation, cheap and expensive alike. The whole point is that an expensive operation, whose c_i is large, drops Phi enough that the difference Phi(D_i) - Phi(D_{i-1}) is very negative and absorbs the spike.
Notice the division of labour. Rules 1 and 2 are about the potential function alone and guarantee that amortized cost is a legitimate upper bound on real cost. Rule 3 is the per-operation work where the analysis actually pays off. If all three hold and every a_i is at most some bound A, then the whole sequence of n operations costs at most n times A in real time, and you have proven an amortized bound of A per operation.
Two case studies, one number each
Take the binary counter you met in the aggregate-method guide: an array of bits you increment, where each increment flips a run of trailing 1s to 0 and then sets one 0 to 1. The natural potential is Phi = the number of 1-bits currently in the counter. It starts at 0 (all bits zero) and never goes negative — both honesty rules pass. Now do an increment that flips k trailing 1s to 0 and turns one 0 into a 1. The real cost is k + 1 bit-writes. The potential drops by k (those ones became zeros) and rises by 1 (the new one), a net change of 1 - k. So the amortized cost is (k + 1) + (1 - k) = 2. Every increment, no matter how long its carry chain, has amortized cost exactly 2 — a clean O(1) — and the giant carry that flips a hundred bits is paid for entirely by the hundred deposits that set those bits in the first place.
Now table doubling, the growable array that doubles its capacity when full. Most insertions are O(1), but the one that overflows must copy all n existing items into a new array of twice the size — an O(n) spike. A potential that works is Phi = 2 * (number of items) - (capacity). Right after a doubling the table is half full, so 2 * (n/2) - n = 0; right before the next doubling the table is full, so Phi has climbed to 2n - n = n, exactly the credit needed to pay for copying n items. Each cheap insert adds one item and pushes Phi up by 2, banking the cost of its own eventual move plus the move of one older item. When the expensive copy finally fires, its O(n) real cost is cancelled almost exactly by an O(n) drop in potential, and the amortized cost lands at a constant. The full numbers are the subject of the final guide in this rung; here the lesson is simply how one well-chosen number tames the whole sequence.
What it gives you, and what it does not
The potential method is the workhorse of advanced amortized analysis precisely because the telescoping sum is mechanical: once you commit to a Phi, the bound either falls out or it does not, with no need to track scattered credits by hand. It scales to structures where the accounting method would drown in bookkeeping — it is the standard tool for analysing splay trees, Fibonacci heaps, and the deep near-constant bound for the union-find structure you will meet in the next guide. The same telescoping argument also underlies the earlier aggregate method, which is really the special case where you bound the whole sum directly instead of one operation at a time.
Be honest about two limits. First, the method tells you nothing about how to find Phi — choosing a potential function is a genuine act of insight, and a poorly chosen Phi will give a true but useless bound, or fail rules 1 and 2 entirely. The cancellation is automatic; the cleverness is in the choice. Second, and just as important, an amortized O(1) bound is a guarantee about the total cost of a whole sequence, not a promise about any single operation. The table-doubling copy that touches all n items genuinely takes Theta(n) time the moment it runs — your user waiting on that one insert feels every microsecond of it.
That last point is the line where amortized and average-case analysis part ways, and it is worth pinning down. An amortized bound is a worst-case statement: it holds for every sequence of operations, with no assumption about randomness or input distribution. Average-case analysis, by contrast, averages over a distribution of inputs and can be wrecked by an unlucky one. So amortized cost is the stronger and more trustworthy guarantee — it just guarantees the average over a sequence, never the timing of one operation within it. Keep that distinction sharp, and the potential method becomes one of the most reliable tools you own.