The Potential Method

The potential method is the most powerful amortised analysis technique. It defines a potential function $\Phi$ mapping each state of the data structure to a real number, representing “stored energy”. Changes in potential pay for work.

Definition

A potential function $\Phi: \Omega \to \mathbb{R}$ maps each possible data structure state to a real number, satisfying:

1. $\Phi(D_0) = 0$ for the initial (empty) state $D_0$
2. $\Phi(D) \ge 0$ for all states $D$

For an operation that transforms state $D_{i-1}$ to $D_i$ with actual cost $c_i$, the amortised cost is:

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

Proof of Correctness

For a sequence of $m$ operations, starting from $D_0$:

$\sum_{i=1}^{m} \hat{c}_i = \sum_{i=1}^{m} \big(c_i + \Phi(D_i) - \Phi(D_{i-1})\big) = \sum_{i=1}^{m} c_i + \Phi(D_m) - \Phi(D_0)$

Since $\Phi(D_0) = 0$ and $\Phi(D_m) \ge 0$, we have:

$\sum_{i=1}^{m} \hat{c}_i \ge \sum_{i=1}^{m} c_i$

The total amortised cost bounds the total actual cost. This is the potential theorem.

Interpretation

• $\Delta\Phi > 0$: the structure becomes “messier” (higher potential); the amortised cost exceeds the actual cost, “saving up” to pay for future cleanup
• $\Delta\Phi < 0$: cleanup occurs, releasing potential to pay for the current operation

Think of $\Phi$ as a measure of “disorder” in the data structure, or as a bank balance tracking stored credit.

Example: Binary Counter

Let $\Phi(D) = \text{number of 1's in the counter}$.

• $\Phi(D_0) = 0$ (counter starts at 0, no 1’s)
• $\Phi(D) \ge 0$ always (count of bits cannot be negative)

Consider an INCREMENT where $t$ trailing 1’s flip to 0 and one 0 flips to 1. Actual cost: $c = t + 1$.

Change in potential:

• Before: $b_{i-1}$ ones
• After: $b_{i-1} - t + 1$ ones (removed $t$ ones, added one)
• $\Delta\Phi = (b_{i-1} - t + 1) - b_{i-1} = 1 - t$

Amortised cost:

$\hat{c} = c + \Delta\Phi = (t + 1) + (1 - t) = 2$

Amortised per INCREMENT: $O(1)$.

This matches the accounting method result (charge 2 per increment). The potential method generalises the accounting intuition into a formal proof technique.

Choosing a Potential Function

Good potential functions often:

1. Measure “disorder” that expensive operations will clean up (e.g. number of trees in a binomial heap root list, number of marked nodes in a Fibonacci heap)
2. Increase smoothly with cheap operations and drop sharply during expensive cleanup
3. Are non-negative and start at zero

For a dynamic array, $\Phi = 2 \cdot \text{size} - \text{capacity}$ works (see Dynamic Arrays Example).

For Fibonacci heaps, $\Phi = \text{numRoots} + 2 \cdot \text{numMarkedNodes}$ (see Binomial Heap Amortized Analysis).

Summary

Aspect	Detail
$\Phi(D)$	Potential: “stored energy” in state $D$
$\hat{c}_i$	$c_i + \Phi(D_i) - \Phi(D_{i-1})$
Requirement	$\Phi(D_0) = 0$, $\Phi(D) \ge 0$
Total bound	$\sum \hat{c}_i \ge \sum c_i$
Key insight	$\Phi$ rises during cheap ops, drops during expensive cleanup

Past Tripos: y2024p1q9, y2023p2q7.