In algorithm analysis, you may encounter situations where a single operation is slow (e.g., dynamic table resizing, bulk pop from a stack), yet the total time of a sequence of operations is far less than the sum of worst‑case costs. Amortized analysis is designed for such problems, and the potential method, with its intuitive “energy” perspective, is one of the most powerful tools. This article walks through classic examples—stacks, binary counters, dynamic tables—showing how to define a potential function, compute amortized costs, and grasp the general principles for designing potential functions. Whether you are a beginner or an experienced developer, you will learn to view the average cost of operation sequences through the lens of potential.
Why Amortized Analysis?
Consider a stack that supports push, pop, and multipop. A single multipop can cost $O(n)$ in the worst case. If every operation were a multipop, the total cost would be $O(n^2)$. In real operation sequences, however, multipop is always preceded by enough pushes, so the total cost is actually $O(n)$. Amortized analysis proves an upper bound like this: no matter the sequence, the total cost is bounded by a value proportional to the number of operations.
There are three equivalent methods: aggregate, accounting, and potential. This article focuses on the potential method because it is best suited for complex data structures.
Core Idea of the Potential Method
Inspired by physics, we define a potential function $\Phi(S)$ that depends only on the current state $S$. For the $i$‑th operation, the amortized cost $\hat{c}_i$ is defined as
[ \hat{c}i = c_i + \Phi(S_i) - \Phi(S{i-1}) ]
where $c_i$ is the actual cost and $\Phi(S_i) - \Phi(S_{i-1})$ is the change in potential.
Intuitively, an operation that consumes a lot of resources (high actual cost) can “spend” some potential, lowering its amortized cost; conversely, a cheap operation can “store” potential to pay for future expensive ones. The motto is: let operations with large consumption decrease the potential significantly.
If the initial potential $\Phi(S_0) = 0$ and $\Phi(S) \ge 0$ for all reachable states, then the total amortized cost is an upper bound on the total actual cost. Thus, if each operation has amortized cost $O(1)$, the total actual cost for $n$ operations is $O(n)$.
General Steps
- Choose a potential function – define a non‑negative $\Phi$ based on the data structure, with $\Phi(S_0) = 0$.
- Verify non‑negativity – ensure $\Phi(S) \ge 0$ after any operation.
- Compute amortized cost for each operation – for each operation type, calculate actual cost $c_i$ and $\Delta\Phi$, then obtain $\hat{c}_i = c_i + \Delta\Phi$.
- Bound the amortized cost – if every operation’s amortized cost is bounded by a constant, the total actual cost is bounded by the total amortized cost, giving the amortized complexity.
Classic Examples
Example 1: Stack with push, pop, multipop
- Potential function: $\Phi(S) =$ number of elements in the stack.
- Initial state: empty stack, $\Phi = 0$.
- Operation analysis:
- push(x): actual cost $1$, stack size increases by $1$ → $\Delta\Phi = +1$ → amortized cost $= 1 + 1 = 2$.
- pop(): actual cost $1$, stack size decreases by $1$ → $\Delta\Phi = -1$ → amortized cost $= 1 - 1 = 0$.
- multipop(k): removes $t = \min(k, \text{size})$ elements, actual cost $t$, $\Delta\Phi = -t$ → amortized cost $= t - t = 0$.
- Conclusion: All operations have amortized cost $O(1)$, so $n$ operations cost $O(n)$ in total.
Example 2: Binary counter increment
- Potential function: $\Phi(S) =$ number of $1$‑bits in the binary representation.
- Initial state: $0$, $\Phi = 0$.
- Operation analysis: An increment flips $t$ bits (the trailing ones become $0$, and the next $0$ becomes $1$). Actual cost $= t$. The change in potential: we lose $(t-1)$ ones and gain one $1$ → $\Delta\Phi = 2 - t$. Amortized cost $= t + (2 - t) = 2$.
- Conclusion: Each increment has amortized cost $2$, so $n$ increments cost at most $2n$, i.e., $O(n)$.
Example 3: Dynamic table insertion
- Potential function: $\Phi = 2n - m$, where $n$ is the current number of elements and $m$ is the table capacity.
- Initial state: empty table, $n = 0$, $m = 0$, $\Phi = 0$.
- Operation analysis:
- Insert without resizing: actual cost $1$, $n$ increases by $1$, $m$ unchanged → $\Delta\Phi = +2$ → amortized cost $= 1 + 2 = 3$.
- Insert triggering resize: suppose the table is full ($m = n$) before insertion. After insertion, $n' = n+1$, and we resize to $m' = 2n$. Actual cost $= n$ (copy) $+ 1$ (insert) $= n+1$. Before insertion, $\Phi = 2n - n = n$. After insertion, $\Phi' = 2(n+1) - 2n = 2$. $\Delta\Phi = 2 - n$. Amortized cost $= (n+1) + (2 - n) = 3$.
- Conclusion: Insert always has amortized cost $3$, giving amortized $O(1)$ per insertion.
Example 4: Dynamic table shrinkage (overview)
If the table supports deletion and halves its capacity when the load factor $n/m < 1/4$, one can define a suitable variant of the potential function (e.g., $|2n - m|$) so that both insert and delete have constant amortized cost. The detailed analysis can be found in Introduction to Algorithms; the core idea is that expensive resize/shrink operations consume potential while cheap operations accumulate it.
How to Design a Potential Function
From the examples, some guidelines emerge:
- Identify “degrading” operations – operations that make the structure larger or more complex (e.g., push, insert) should accumulate potential.
- Identify “restoring” operations – operations that consume resources and simplify the structure (e.g., multipop, resize) should consume potential.
- Keep $\Phi$ non‑negative and start at $0$ – required for the theorem to hold.
- Common candidates:
- Stack / queue: number of elements.
- Binary counter: number of $1$‑bits.
- Dynamic table: $2n - m$ (or its absolute value).
- Tree structures: sum of logarithms of subtree sizes (e.g., Splay trees).
- Others: count of elements greater than $1$, number of trailing zeros, etc.
Extensions: Broad Applications
Potential analysis is widely used beyond the examples above:
- Splay trees: potential $= \sum \log(\text{size of subtree})$, proving $O(\log n)$ amortized cost per operation.
- Range square‑root updates: using segment trees, each effective modification reduces element values, and potential analysis bounds total work by $O((n+q) \log n)$.
- Dynamic table with deletions: combining expansion and contraction, potential analysis shows amortized $O(1)$ for all operations.
The underlying principle is the same: spread the cost of expensive operations over many cheap ones, yielding a tighter overall bound.
Caveats and Next Steps
- Amortized ≠ worst‑case per operation: amortized $O(1)$ means the average over a sequence is $O(1)$; individual operations may still be $O(n)$. Real‑time systems must consider worst‑case latency.
- Verification: for a custom potential function, you can simulate operation sequences with a small program, summing actual costs and amortized costs to confirm that total actual $\le$ total amortized.
- Next steps: try applying the potential method to other structures, such as union‑find with path compression or segment tree range updates. Remember the motto: let operations with large consumption decrease the potential significantly!