Potential Method for Amortized Analysis, in depth: defining the potential, binary counters, growth factors, shrinking without thrashing and testing a potential in code

The definition and why it works

Let D₀ be the initial state of a data structure and D_i its state after the i-th operation, whose actual cost is c_i. Choose a potential function Φ that maps each state to a real number. The amortized cost of operation i is defined as

a_i = c_i + Phi(D_i) - Phi(D_{i-1})

Sum over n operations and the potential terms telescope: every intermediate Φ(D_i) appears once with a plus sign and once with a minus sign.

sum(a_i, i=1..n) = sum(c_i, i=1..n) + Phi(D_n) - Phi(D_0)

So if Φ(D_n) ≥ Φ(D₀) for every n, the total amortized cost is an upper bound on the total actual cost. The usual way to guarantee that is to set Φ(D₀) = 0 and prove Φ(D) ≥ 0 for every reachable state. Then if you show a_i ≤ k for every operation, any sequence of n operations costs at most kn.

Read Φ as stored energy. A cheap operation that leaves the structure closer to an expensive event raises the potential, so its amortized cost exceeds its actual cost. The expensive event releases potential, and the drop pays for the work. Compared with the accounting method, where credits sit on individual elements, the potential is a single number computed from the whole state, which is what makes it work for structures like splay trees where no element-level bookkeeping is natural.

Example: the binary counter

A k-bit binary counter starts at zero. Increment flips trailing 1s to 0 until it finds a 0, which it sets to 1. If there are t trailing 1s, the actual cost is t + 1 bit flips. In the worst case t = k - 1, so a naive bound for n increments is O(nk).

Choose Φ = the number of 1 bits. It starts at 0 and is never negative. An increment with t trailing ones turns t ones into zeros and one zero into a one, so the potential changes by 1 - t. The amortized cost is

a = (t + 1) + (1 - t) = 2

n increments therefore cost at most 2n flips in total, no matter how long any single increment is. Notice what the potential captured: the trailing ones are exactly the debt a future increment will have to pay, so counting ones measures pending work. That is the general shape of a good potential.

Example: the dynamic array and any growth factor

A dynamic array stores num elements in a buffer of capacity cap. Appending to a non-full buffer costs 1. Appending to a full buffer allocates capacity 2·cap (or 1 if cap is 0), copies num elements and writes the new one, at cost num + 1. Choose

Phi = 2 * num - cap

After the first append the buffer is always at least half full, so num ≥ cap/2 and Φ ≥ 0; it starts at 0 for an empty array with capacity 0. For an append without a resize, num rises by 1 and cap is unchanged, so Φ rises by 2 and the amortized cost is 1 + 2 = 3. For an append that resizes from a full buffer of capacity c, before the operation Φ = 2c - c = c, and after it Φ = 2(c + 1) - 2c = 2. The amortized cost is (c + 1) + 2 - c = 3. Every append costs 3 amortized, so n appends cost at most 3n.

The same argument works for any growth factor g > 1. Use Φ = (g / (g - 1))(num - cap/g). A resize from capacity c releases exactly enough potential to pay for copying c elements, and every append comes out at 1 + g/(g - 1), assuming exact capacities. Doubling gives 3. A factor of 1.5 gives 4. A factor of 1.125 gives 10. Smaller factors waste less memory and pay more copying per element; that is the trade every runtime makes. CPython's list grows by about one eighth plus a small constant; Go's slices grow about 2x while small and taper toward 1.25x as they get large. Both still give constant amortized append, with different constants. Hash tables make the same choice when they rehash on a load factor threshold.

Worked example: ten appends

Run ten appends from an empty array with capacity 0. Each row shows the state after the operation.

Actual costs sum to 25. Amortized costs sum to 2 + 9 × 3 = 29. The difference is the final potential: 29 = 25 + 4 - 0, exactly the telescoping identity. The 4 units of potential left over are prepaid copying for the next resize at append 17.

Shrinking without thrashing

Supporting pop with shrinking exposes the classic trap. If you halve the capacity whenever the array drops to half full, an adversary alternates push and pop at the boundary: each push doubles, each pop halves, and every operation copies about n elements. No potential can save that design, because the cost really is Θ(n) per operation.

The fix is hysteresis: grow when full, shrink to half only when the load factor α = num/cap falls below 1/4. After any resize the load factor is 1/2, so at least cap/4 operations must happen before the next one. A potential that captures this is

Phi = 2 * num - cap      if alpha >= 1/2
Phi = cap / 2 - num      if alpha <  1/2

It is zero right after a resize, grows as the array moves away from half full in either direction, and reaches enough to pay for the copy at either threshold. The standard textbook analysis shows every push and pop has amortized cost at most 3. Production containers often skip automatic shrinking and expose a shrink-to-fit call instead, which moves the decision to the programmer.

A recipe for choosing a potential

1. Find the expensive event. Resize, cascade of carries, long rotation path, consolidation of trees.
2. Find what makes it expensive. The number of elements to copy, trailing ones, tree imbalance, number of roots.
3. Write Φ as a multiple of that quantity, shifted so that it is zero in the initial state and right after the expensive event.
4. Prove Φ ≥ 0 for every reachable state. If it can go negative, the bound is not valid.
5. Compute a = c + ΔΦ for each operation type, case by case, and pick the multiplier so the expensive case comes out constant (or logarithmic).

Two famous results follow this recipe. For splay trees, let s(x) be the size of x's subtree and use Φ = Σ log₂ s(x). The access lemma shows that splaying x in a tree rooted at t costs at most 3(log s(t) - log s(x)) + 1 amortized, which is O(log n). For Fibonacci heaps, use Φ = t(H) + 2m(H), where t counts root-list trees and m counts marked nodes; that gives O(1) amortized insert and decrease-key and O(log n) extract-min. The O(1) decrease-key is what lets Dijkstra's algorithm reach O(E + V log V) in theory, although binary heaps, covered in Heap Operations, usually win in practice. The near-constant bound for Union-Find with path compression is also an amortized result.

Testing a potential in code

A potential argument is a proof, but you can test it cheaply. Instrument the structure to report actual cost, compute Φ from its state after each operation, and assert both invariants over random and adversarial sequences. A bug in either the code or the potential shows up as a violated assertion with the exact step.

import random

class DynArray:
    def __init__(self):
        self.buf, self.num = [], 0       # len(buf) is the capacity

    def append(self, x):
        cost = 1
        if self.num == len(self.buf):
            new = [None] * max(1, 2 * len(self.buf))
            new[:self.num] = self.buf[:self.num]
            cost += self.num                 # one unit per element copied
            self.buf = new
        self.buf[self.num] = x
        self.num += 1
        return cost

def phi(a):
    return 2 * a.num - len(a.buf)

def check(ops=100_000, bound=3, seed=0):
    random.seed(seed)
    a, prev, actual, amort = DynArray(), 0, 0, 0
    for i in range(ops):
        c = a.append(random.random())
        now = phi(a)
        assert now >= 0, f"potential negative at op {i}"
        assert c + now - prev <= bound, f"amortized {c + now - prev} > {bound} at op {i}"
        actual, amort, prev = actual + c, amort + c + now - prev, now
    assert actual <= amort
    return actual, amort

print(check())   # actual stays below 3 * ops

Extend the harness with pop and the two-piece potential above, then feed it the push-pop sequence at the boundary. If you set the shrink threshold to 1/2 by mistake, the amortized assertion fails within a few operations, which is exactly the thrashing case.

Amortized cost in production systems

Amortized bounds describe throughput, not latency. A doubling array that has 100 million elements copies them all on one append, and that single request sees the full cost. Systems with tail-latency budgets therefore de-amortize: they spread the expensive work across many cheap operations. Incremental rehashing keeps two tables and moves a few buckets on each operation; log-structured stores bound how much compaction runs per write (see LSM Tree Compaction Architecture); garbage collectors do the same with incremental and concurrent marking. The potential argument still tells you the total work is linear; the engineering decides when it is paid.

Amortized bounds also assume the sequence runs forward from one state. If you snapshot a structure and replay operations from the snapshot repeatedly, as persistent data structures, undo stacks or backtracking search do, an adversary can return to the state just before a resize and trigger it again and again. Potential that was spent once is spent many times. Persistence needs worst-case or lazily evaluated structures instead.

Failure modes

• Negative potential. Forgetting the initial state, so Φ starts below zero and the telescoped sum no longer bounds the actual cost.
• Potential that ignores an operation. Proving push and forgetting that pop or clear can change Φ in the other direction.
• Thrashing thresholds. Growing and shrinking at the same load factor, which no potential can rescue.
• Confusing amortized with average. Amortized bounds are worst case over sequences, with no probability; expected-time bounds for hashing are a different claim.
• Using amortized bounds for latency SLOs. One resize can blow a p99 budget even though throughput is fine.

Trade-offs

The aggregate method (sum the total cost directly) is simplest when all operations are the same type. The accounting method is intuitive when you can attach credits to specific elements. The potential method costs more thought up front, but it handles mixed operation types and global structure, and the proof doubles as a test oracle, as the harness shows. On the data structure side, larger growth factors buy cheaper amortized appends with more memory slack; de-amortized designs buy predictable latency with more code and higher constants.

What to do next

1. Redo the binary counter with Φ = number of ones and confirm the amortized cost of 2 by hand for 0 to 15.
2. Run the harness above, then switch to growth factor 1.5 with the general potential; explain why integer capacities push the measured maximum slightly above 4.
3. Add pop with shrinking at 1/4 and the two-piece potential; then set the threshold to 1/2 and watch the assertion fail.
4. Write down the potential for a stack with multipop (Φ = stack size) and prove every operation is O(1) amortized.
5. Find one structure in your own code base that resizes or compacts, and check whether its worst single operation fits your latency budget.
6. Read the splay tree access lemma with Φ = Σ log s(x) and trace one zig-zig step's change in potential.