Amortized Analysis: Accounting and Potential Methods

Amortized analysis assigns a cost to each operation in a sequence so that the sum of assigned costs upper-bounds the sum of actual costs, even though individual assigned costs need not match individual actual costs. The aggregate method computes this bound by analyzing the whole sequence at once and dividing by the number of operations. It is often the simplest first attack, but it gives only an average over the whole sequence and provides no structural explanation of why the bound holds, and it becomes unwieldy when operations have heterogeneous types (e.g., `push`, `pop`, `multipop` with different natural costs). The accounting method fixes this by assigning an amortized cost $\hat{c}_i$ to the $i$-th operation, chosen by the analyst, such that whenever $\hat{c}_i$ exceeds the true cost $c_i$, the surplus $\hat{c}_i - c_i$ is stored as credit on specific objects in the structure (e.g., "each array slot holds 1 credit after being written"). Later, when an operation's true cost exceeds its amortized cost, the deficit is paid for by spending previously stored credit. The central invariant that must be maintained is:

If this invariant holds after every operation, then summing over the whole sequence gives $\sum \hat{c}_i \ge \sum c_i$, because the credit balance (which starts and never dips below 0) absorbs exactly the gap between amortized and actual costs. Hence $\sum \hat{c}_i$ is a valid upper bound on total actual cost, and the amortized cost per operation is simply $\hat{c}_i$. The potential method abstracts this idea one level further. Instead of tracking credit on individual objects, define a single real-valued function $\Phi$ of the entire state of the data structure, called the potential. Let $D_0$ be the initial structure and $D_i$ the structure after the $i$-th operation. Define the amortized cost of operation $i$ as

Summing telescopically over $n$ operations:

If we choose $\Phi$ so that $\Phi(D_0) = 0$ and $\Phi(D_i) \ge 0$ for all $i$, then $\Phi(D_n) - \Phi(D_0) \ge 0$, which gives $\sum \hat{c}_i \ge \sum c_i$ — exactly the bound we want. The potential plays the role of "total credit in the bank"; it need not correspond to any physically stored tokens, only to a mathematical accounting quantity satisfying non-negativity.

Designing an accounting-method proof. The recipe has four steps: 1. Identify a natural unit of "work debt" in the structure (e.g., an unwritten array slot, a 1-bit in a counter, an element on a stack). 2. Propose an amortized cost $\hat{c}_i$ for each operation type, usually a small constant or a simple expression. 3. Verify, operation by operation, that $\hat{c}_i - c_i$ correctly deposits or withdraws credit against the objects you identified, and that no object's credit balance (nor the total) goes negative. 4. Conclude $\sum c_i \le \sum \hat{c}_i$, giving the amortized bound per operation.

Designing a potential-method proof. The recipe: 1. Define $\Phi$ as an explicit function of the data structure's state — a count, a sum, a measure of "disorder" or "imbalance." 2. Check $\Phi(D_0) = 0$ (or more generally, that $\Phi$ never drops below its initial value — some presentations only require $\Phi(D_i) \ge \Phi(D_0)$ for all $i$). 3. For each operation type, compute $\hat{c}_i = c_i + \Delta\Phi_i$ symbolically, in terms of the state just before the operation. 4. Show this simplifies to a clean bound (e.g., $O(1)$), for every possible state, not just typical ones — this is the crux of correctness. ```text PSEUDOCODE: Potential-method template for proving an amortized bound Input: a sequence of operations op_1, ..., op_n on structure D, with real costs c_1,...,c_n Define: a potential function Phi(D) computable from D's current state procedure ANALYZE-SEQUENCE(D_0, op_1..op_n): Phi_prev <- Phi(D_0) assert Phi_prev == 0 // or >= baseline, per chosen convention total_actual <- 0 total_amortized <- 0 for i = 1 to n: c_i <- true cost of applying op_i to D_{i-1} // measured, e.g. #elementary steps D_i <- result of applying op_i to D_{i-1} Phi_i <- Phi(D_i) delta <- Phi_i - Phi_prev c_hat_i <- c_i + delta // this is the amortized cost, derived not assumed total_actual <- total_actual + c_i total_amortized <- total_amortized + c_hat_i assert Phi_i >= 0 // potential invariant: must hold for EVERY reachable D_i Phi_prev <- Phi_i // Telescoping identity (always true by construction): // total_amortized = total_actual + Phi_n - Phi_0 // Since Phi_n >= 0 = Phi_0, we get: // total_actual <= total_amortized return total_amortized // valid upper bound on total_actual ``` ```text PSEUDOCODE: Dynamic array PUSH, analyzed by both methods side by side state: array A of capacity cap, size n (initially cap = 1, n = 0) procedure PUSH(x): if n == cap: cap' <- 2 cap allocate new array A' of capacity cap' copy all n elements from A to A' // costs n elementary copy operations A <- A', cap <- cap' A[n] <- x n <- n + 1 // true cost c_i = 1 (the write) + n if a resize just happened, else 1 // ACCOUNTING METHOD // charge amortized cost c_hat = 3 per push. // 1 unit pays for writing the new element. // 2 units are stored as credit ON the new element itself. // invariant: every "live" element holds >=0 credit, and elements in the // second half of the array (indices n/2 .. n-1) hold exactly 2 credits. // when a resize is triggered (n == cap), the n/2 elements added since the // last resize each contribute their stored 2 credits -> 2(cap/2) = cap credits, // exactly enough to pay the copy cost of the (now) cap elements. Credit resets to 0. // POTENTIAL METHOD // Phi(D) = 2n - cap // Phi_0 = 2(0) - 1 = -1 -> shift convention or start cap=0; assume Phi_0 = 0 for simplicity // Case A (no resize): c_i = 1, Phi increases by 2 (n -> n+1, cap unchanged) // c_hat_i = 1 + 2 = 3 // Case B (resize triggers, n == cap before push): c_i = n + 1 (copy + write) // cap doubles: cap -> 2n ; n -> n+1 // Phi_before = 2n - n = n ; Phi_after = 2(n+1) - 2n = 2 // c_hat_i = (n+1) + (2 - n) = 3 // Both cases give c_hat_i = 3 = O(1), matching the accounting method exactly. ``` The two derivations above are not a coincidence: the potential function $\Phi(D) = 2n - \text{cap}$ is precisely a closed-form expression for "total stored credit" in the accounting proof. This is the general pattern — a well-designed potential function is the accounting scheme's credit ledger, compressed into a single formula.

Why the invariant proves the bound. Both methods rest on the same telescoping trick. In the accounting method, let $\text{credit}_i$ denote total stored credit after operation $i$, with $\text{credit}_0 = 0$. By construction $\text{credit}_i = \text{credit}_{i-1} + (\hat{c}_i - c_i)$, so

If we maintain $\text{credit}_i \ge 0$ for all $i$ (the whole content of the correctness proof), then $\sum \hat{c}_i - \sum c_i = \text{credit}_n \ge 0$, i.e. $\sum c_i \le \sum \hat{c}_i$. This is an exact algebraic identity, not an approximation — the only "proof obligation" is the non-negativity check at every step, which must be argued for arbitrary, not just typical, operation sequences. The potential method is the identical argument with $\Phi(D_i)$ playing the role of $\text{credit}_i$. The requirement $\Phi(D_i) \ge \Phi(D_0)$ for every reachable $D_i$ is the entire correctness burden. Crucially, this must hold for every sequence of operations the adversary could choose, not just the sequence you happen to trace through by hand — the proof is over all reachable states, universally quantified.

Equivalence of the two methods. Any accounting-method proof induces a potential function: define $\Phi(D) =$ total credit stored in $D$ under the accounting scheme. Conversely, any potential function induces an accounting scheme: treat $\Phi(D_i)$ itself as "credit currently in the bank" (not tied to specific objects, but to the aggregate state). The two frameworks have equal expressive power; the choice between them is a matter of which is easier to compute and verify for a given structure. Accounting is often more intuitive when credit has an obvious physical meaning (an unspent token per array slot); potential functions are often algebraically cleaner and easier to manipulate symbolically (e.g., for splay trees, where $\Phi = \sum \log(\text{subtree sizes})$ has no simple "per-object credit" story but is easy to bound analytically).

Complexity honesty. Amortized bounds are guarantees on the total cost of any sequence of $n$ operations, divided by $n$. They are not:

• A worst-case bound on any single operation (a resize really does cost $\Theta(n)$ that one time).
• An average-case or expected bound over random inputs — amortized bounds hold for every sequence, adversarial or not, with no probability involved.
• Valid if the adversary can inspect and exploit internal state across independent data structures sharing credit — amortized bounds are for a single structure evolving through a sequence of operations on itself (though they do compose: $k$ independent structures each with $O(1)$ amortized cost give $O(k)$ total).

For the dynamic array, the amortized $O(1)$ per push yields a worst-case total of $O(n)$ for $n$ pushes starting empty — this is the real payoff: even though individual pushes can cost $\Theta(n)$, no adversarial sequence of $n$ pushes can cost more than $O(n)$ total, because doubling geometrically means total copying work is $\sum_{k} 2^k \le 2n = O(n)$.

We trace a binary counter supporting `INCREMENT`, incrementing a $k$-bit binary number by flipping bits according to the ripple-carry rule (flip the lowest-order 0 bit to 1, flip every 1 bit below it to 0). The true cost of one increment is the number of bits flipped.

Potential function: $\Phi(D) = b(D)$, the number of 1-bits currently in the counter. Clearly $\Phi(D) \ge 0$ always, and $\Phi(D_0) = 0$ for the all-zero start.

Cost analysis of one increment. Suppose the increment flips $t$ trailing 1-bits to 0, then flips one 0-bit to 1 (if the counter was all 1s, it flips all $k$ bits to 0, but we track only bits that existed — standard treatment assumes no overflow, or that overflow simply resets $b$ to 0). True cost $c_i = t + 1$. Change in potential: $b$ decreases by $t$ (the flipped 1s) and increases by 1 (the new 1), so $\Delta\Phi = 1 - t$. Then

Every increment has amortized cost exactly $2 = O(1)$, regardless of $t$. Summing over $n$ increments starting from counter value 0 (so $\Phi(D_0)=0$ and $\Phi(D_n) \ge 0$):

So $n$ increments cost $O(n)$ total, i.e. $O(1)$ amortized per increment — matching the intuition that low-order bits flip every time, but higher bits flip exponentially less often.

Total actual cost over these 7 increments: $1+2+1+3+1+2+1 = 11$. Total amortized cost: $2 \times 7 = 14 \ge 11$. The bound holds, with slack equal to $\Phi(D_7) - \Phi(D_0) = 3 - 0 = 3$, exactly matching $14 - 11 = 3$ — the telescoping identity checks out exactly, as it must by construction. Now contrast with the accounting-method version of the same problem, to show the equivalence concretely: charge amortized cost 2 per increment; deposit 1 credit on each bit as it is set to 1 (paying for the eventual cost of flipping it back to 0), and use the other 1 unit to pay for setting that bit. When a lower-order 1-bit is flipped to 0 during a later increment, spend its stored credit to cover that flip — cost already paid for. Since every bit that gets flipped to 0 was previously flipped to 1 with a deposited credit, the balance never goes negative. This is exactly the credit ledger whose total equals $b(D) = \Phi(D)$.

The accounting and potential methods emerged from the broader development of amortized analysis as researchers sought rigorous tools to analyze self-adjusting and dynamically resized data structures in the 1980s.

Standard library dynamic arrays — C++'s `std::vector`, Java's `ArrayList`, Python's `list` — all rely on geometric (usually doubling or 1.5×) growth precisely because the potential-method argument guarantees amortized $O(1)$ append despite occasional $O(n)$ reallocation. Disjoint-set (union-find) structures with union-by-rank and path compression, used in Kruskal's minimum spanning tree algorithm, in compiler register-allocation interference graphs, and in image-segmentation connected-component labeling, achieve their near-linear total running time via a potential-function argument bounding the (inverse-Ackermann) amortized cost per operation. Splay trees, used in some cache and memory-management implementations for their self-adjusting locality properties, are correct and efficient only because of a potential-function proof over subtree sizes. Amortized reasoning also underlies the analysis of hash table resizing (open addressing and chaining implementations resize using the same doubling argument as dynamic arrays), incremental garbage collectors that spread work across allocations, and the competitive-ratio proofs for online caching and scheduling algorithms, which reuse the identical telescoping-potential technique. Understanding these two methods is also a direct stepping stone toward analyzing comparison-based algorithms' inherent limits, as in Comparison-Based Sorting Lower Bounds, where potential-like counting arguments (information-theoretic entropy bounds) play an analogous role in proving that no algorithm can do better than a stated bound.

Ask the tutor: Can you show how the potential method extends to prove amortized $O(\log n)$ bounds for splay tree operations?