The Potential Method

The accounting method tracks credit coin by coin, glued to individual elements. That works, but it can get fiddly: which element holds which credit, and does the bank stay solvent? The potential method is the same idea made elegant and mechanical. Instead of scattering credit across elements, we summarise the entire "stored-up work" of the data structure in a single number — a potential function \Phi, like the potential energy of a stretched spring or the balance of a bank account.

Cheap operations do a little extra work that raises the potential (charging the spring); the rare expensive operation releases that stored potential to pay for itself. It is the most powerful and widely used of the amortisation techniques — the tool of choice for analysing splay trees, Fibonacci heaps, and union–find — precisely because you get to design one clever function and then let the algebra do all the bookkeeping.

The definition, and the telescoping trick

Let D_0 be the initial data structure and D_i the result after the i-th operation, whose actual cost is c_i. Pick any function \Phi that maps a data-structure state to a real number. The amortised cost of operation i is defined to be the actual cost plus the change in potential:

\hat{c}_i \;=\; c_i \;+\; \Phi(D_i) - \Phi(D_{i-1}).

Why is this useful? Sum it over a whole sequence and the potential terms telescope — each \Phi(D_i) appears once with a plus and once with a minus, and everything cancels except the endpoints:

\sum_{i=1}^{n}\hat{c}_i \;=\; \sum_{i=1}^{n} c_i \;+\; \Phi(D_n) - \Phi(D_0).

So the total amortised cost equals the total actual cost, corrected only by the net change in potential from start to finish. Rearranging, the real total we actually care about is

\sum_{i=1}^{n} c_i \;=\; \sum_{i=1}^{n}\hat{c}_i \;-\; \big(\Phi(D_n) - \Phi(D_0)\big).

The one condition that makes it a valid bound

If \Phi(D_i) \ge \Phi(D_0) for every i, then \Phi(D_n) - \Phi(D_0) \ge 0, and therefore \sum c_i \le \sum \hat{c}_i.
In words: the sum of amortised costs is a genuine upper bound on the real total. Bound each \hat{c}_i by a constant and you have bounded the whole sequence.
The usual convenient choice is \Phi(D_0) = 0 and \Phi \ge 0 always — then you are automatically safe, because the potential starts at zero and never goes below it.

This is exactly the banker's "credit never goes negative" rule, wearing a mathematician's hat: \Phi(D_i) - \Phi(D_0) is the total credit stored in the structure. The potential method just hands you a formula instead of a ledger. The intuition is a spring: as long as the spring never ends up more compressed than it started, all the energy you fed in is available to be spent.

Worked example 1 — the binary counter, elegantly

Take \Phi(D_i) to be simply the number of 1-bits in the counter. It starts at \Phi(D_0) = 0 and is always \ge 0 — the safety condition is free. Now watch a single increment that clears a run of t trailing 1s and sets one 0 to 1:

Actual cost: c_i = t + 1 bit-flips (clear t ones, set one bit).
Potential change: t ones became zeros and one zero became a one, so \Delta\Phi = 1 - t.
Amortised cost: \hat{c}_i = (t + 1) + (1 - t) = 2. The t vanishes — every increment has amortised cost exactly 2, no matter how long the carry chain.

So n increments cost at most 2n bit-flips — the \Theta(1) amortised bound, with none of the geometric-series bookkeeping. The chart shows the potential \Phi (the number of set bits) rising and falling as the counter runs: it charges up on cheap increments and discharges when a long carry chain fires, but it never drops below its starting value of 0 — which is exactly why the amortised total upper-bounds the real one.

Worked example 2 — a dynamic table that pays for its own resizes

For a growing dynamic array with \text{num} stored items and capacity \text{cap}, choose

\Phi = 2\cdot\text{num} - \text{cap}.

Right after a resize the table is half full (\text{num} = \text{cap}/2), so \Phi = 0 — empty of stored energy. As you push without resizing, \text{num} climbs while \text{cap} stays fixed, so \Phi grows by 2 per push, building up exactly the energy needed. By the time the table is full (\text{num} = \text{cap}), \Phi = \text{cap} — precisely enough stored potential to pay for copying all \text{cap} elements on the next resize.

No resize: actual c_i = 1, \Delta\Phi = 2 (one more item), so \hat{c}_i = 1 + 2 = 3.
Resize (from full): actual c_i = \text{num} copies +\,1 write; the doubling drops \Phi from \text{num} back toward 2, and again \hat{c}_i = 3. The stored potential absorbs the copy cost.

Same answer as the accounting method (3 per push), but derived by a single well-chosen formula that never needed us to say which element holds which coin. That compression of the bookkeeping into one function is the whole appeal of the potential method.

There is no algorithm for guessing \Phi — it is where the creativity lives, and a badly chosen potential simply gives a useless (or invalid) bound while a good one makes the analysis fall out in one line. The reliable heuristic: \Phi should be large exactly when the structure is in a state that makes the next expensive operation likely, so that the potential is high right before you need to spend it. A binary counter is "dangerous" when it is full of 1s (a long carry looms) — so count the 1s. A dynamic table is dangerous when nearly full — so measure fullness. Splay trees use the log of subtree sizes; Fibonacci heaps count trees plus marked nodes. Find the quantity that spikes just before the pain, and the potential method rewards you.

The telescoping identity is always true — but it only gives an upper bound when \Phi(D_n) \ge \Phi(D_0). If you pick a potential that can fall below its starting value, then \Phi(D_n) - \Phi(D_0) is negative and \sum \hat{c}_i can be smaller than the true total — you would be claiming the sequence is cheaper than it really is, a false bound. This is the potential-method twin of letting the bank go into debt. The safe habit, used almost universally, is to insist \Phi(D_0) = 0 and \Phi(D) \ge 0 for all reachable states; then the endpoint condition holds automatically. Always check this first, before you trust a single amortised number.