Skip to main content

Potential Method and Formal Amortized Cost Accounting

What This Concept Is​

The potential method is the most general amortized-analysis technique. It associates with each data-structure state D_i a real number Phi(D_i) called the potential, and defines the amortized cost of the i-th operation as

amortized_i = actual_i + Phi(D_i) - Phi(D_{i-1}) = actual_i + Delta Phi_i.

Provided that Phi(D_0) = 0 and Phi(D_i) >= 0 for all later i, the sum of amortized costs upper-bounds the sum of actual costs:

sum_{i=1}^{n} actual_i <= sum_{i=1}^{n} amortized_i.

The core move is: pick a Phi so that cheap operations increase the potential (storing "potential energy") and expensive operations decrease it (spending the stored energy). The method subsumes both aggregate (take Phi = 0) and accounting (take Phi = sum of credits), so any proof done with those methods can be re-expressed as a potential-function proof. The converse is not true -- splay trees and Fibonacci heaps require the potential method because no natural "credit on elements" view works.

Choosing Phi is the creative step. A good potential has three properties:

  1. Non-negative: Phi(D_i) >= 0 for all reachable states.
  2. Starts at zero: Phi(D_0) = 0 for the initial state of the data structure.
  3. Tracks future cost: Phi(D) is proportional to the "work owed" by the current state -- the potential stored up by cheap operations that will be paid out during expensive ones.

When the proof of Phi >= 0 is hard, reach for the accounting method and interpret Phi as "total credits outstanding"; when the accounting argument is messy, reach for Phi and verify the three properties mechanically.

Why It Matters Here​

Every major amortized result in this module has a potential-function proof:

  • dynamic array: Phi = 2 * (size - capacity/2) when size > capacity/2, else 0
  • union-find with rank and path compression: a sophisticated Phi based on rank levels (Tarjan's proof)
  • Fibonacci heaps: Phi = roots + 2 * marked
  • splay trees and self-adjusting structures: Phi = sum over nodes of log(size of subtree)
  • binary counter: Phi = number of 1-bits

Once you learn to read and propose potential functions, you can adapt the method to new structures. The aggregate and accounting methods are special cases: aggregate corresponds to Phi = 0 everywhere; accounting corresponds to Phi equal to the sum of placed credits.

Concrete Examples​

Example 1 -- dynamic array with doubling. Let s = size, c = capacity, and define

Phi(D) = 2s - c when s >= c/2, else 0.

Check: Phi(D_0) = 0 and Phi(D_i) >= 0 always.

Non-resizing append when s < c:

  • actual cost: 1
  • s increases by 1, c unchanged
  • Delta Phi = 2(s+1) - c - (2s - c) = 2
  • amortized cost: 1 + 2 = 3

Resizing append at s = c:

  • actual cost: s + 1 (copy s old items, store 1 new)
  • before resize: s = c, so Phi_before = 2c - c = c
  • after resize: c_new = 2c, s_new = c + 1. s_new >= c_new/2 iff c + 1 >= c, true, so Phi_after = 2(c + 1) - 2c = 2
  • Delta Phi = 2 - c
  • amortized cost: (c + 1) + (2 - c) = 3

Every append has amortized cost 3 = O(1), matching the aggregate bound.

Example 2 -- binary counter with Phi = number of 1-bits. Let b(D_i) be the number of 1-bits in the counter's state.

An increment that flips k trailing 1-bits to 0 and then sets the next 0-bit to 1:

  • actual cost: k + 1 bit flips
  • before: b bits set, k of them trailing; after: b - k + 1
  • Delta Phi = (b - k + 1) - b = 1 - k
  • amortized cost: (k + 1) + (1 - k) = 2

Every increment has amortized cost 2 = O(1), regardless of how long the carry chain is. Increments with long carry chains are "paid for" by the potential drop when many 1-bits become 0.

Common Confusion / Misconceptions​

"Phi is a physical quantity in the data structure." It is not. The code does not maintain Phi; only the analysis refers to it. Any non-negative function of the state that satisfies Phi(D_0) = 0 can be tried; the only question is whether the resulting amortized costs are nicely bounded.

"Amortized cost is always non-negative." It can be negative for a single operation if Delta Phi_i < -actual_i. Negative amortized costs are allowed; they represent work being "returned" to the potential reservoir. The bound is on sums, not per-operation values.

"If my potential does not give a tight bound, the method has failed." Usually the potential just needs adjusting. Try scaling (multiply by a constant), shifting (subtract a state-dependent minimum), or adding a new term. Proofs that feel stuck often need the potential to account for a dimension you forgot -- e.g., splay tree potential must weight deep nodes more, not equally.

"Potential must be non-decreasing." It must be non-negative. Decreasing is fine -- that is exactly the mechanism by which expensive operations are paid for. A good potential oscillates: cheap ops raise it, expensive ops drain it, balance stays non-negative.

How To Use It​

Four-step template:

  1. propose Phi(D) that grows during cheap operations and shrinks during expensive ones
  2. verify Phi(D_0) = 0 and Phi(D_i) >= 0
  3. for each operation type, compute Delta Phi and hence amortized = actual + Delta Phi
  4. read the per-operation amortized bound off the results

Signs of a good Phi:

  • cheap operations that set up future expensive work raise Phi
  • expensive operations that consume that setup lower Phi
  • the magnitude of Phi matches the work "owed" to the structure

Finding Phi when stuck:

  1. start with "total work saved up" -- the accounting-method credit total
  2. if a natural credit scheme exists, take Phi = sum of credits
  3. if not, pick a structural measurement that captures "bad shape": number of roots, number of marked nodes, log-sum of subtree sizes, imbalance counts
  4. verify the three properties, compute Delta Phi on each operation type, read off amortized cost

Transfer / Where This Shows Up Later​

  • S5 (OS): kernel structures with lazy cleanup (RCU, deferred freelist coalescing) use potential-like reasoning to prove that bursts of reclamation are amortized cheap.
  • S6 (databases): LSM-tree compaction cost is amortized via a potential on "unmerged data"; compactions drain the potential, writes raise it. This is exactly the analysis framework behind write amplification bounds.
  • S7 (architecture): measuring a system's "debt" (tech debt, migration debt, capacity debt) in a quantifiable form is a potential function; incidents drain the potential, planning work raises it. ADRs about when to pay down debt are arguments about Phi >= 0.
  • S8 (scale): adaptive load shedding ("if queue length > threshold, drop requests") is a potential-driven policy -- Phi = queue length, and the shedding policy enforces the non-negative invariant by paying work down.

Check Yourself​

  1. State the identity amortized_i = actual_i + Delta Phi_i and why it gives a valid amortized bound.
  2. What two conditions on Phi are required?
  3. Why are aggregate and accounting methods special cases of the potential method?
  4. Can amortized cost be negative for a single operation? Why or why not?
  5. For the dynamic-array Phi = max(0, 2s - c), why is the factor of 2 necessary -- what breaks if you use s - c/2?
  6. Propose a potential function for a structure you know (hash table with rehashing, deque built on a ring buffer, counting Bloom filter) and verify the three properties.

Mini Drill or Application​

  1. Using the potential Phi = number of 1-bits in the counter, prove amortized O(1) for binary-counter increment.
  2. Define a potential for the two-stack queue (enqueue into A, dequeue from B; when B empty, move A into B). Compute amortized costs.
  3. Starting from the Fibonacci-heap potential Phi = (number of roots) + 2 * (number of marked non-root nodes), compute the amortized cost of one insert and one decrease-key that triggers one cut but no cascade.
  4. For the dynamic array with both grow (on full) and shrink (below 1/4 full, halve capacity), propose a potential that gives O(1) amortized for both append and pop.
  5. Implement a binary counter with an increment() method that also prints Phi = popcount(state) and the amortized cost per increment. Run 10^6 increments and confirm the observed amortized cost stays near the predicted constant.

Read This Only If Stuck​