Amortized Analysis: The Aggregate, Accounting, and Potential Methods

Why Amortized Analysis Is Different From Average-Case Analysis

The average-case analysis discussed earlier in this series, in the context of probabilistic analysis, assumes some probability distribution over inputs and reasons about expected behavior. Amortized Analysis is entirely different: it makes no probabilistic assumptions whatsoever. Instead, it guarantees the average cost per operation over a worst-case sequence of operations, providing a rigorous, deterministic bound rather than a probabilistic expectation.

Motivating Example: The Dynamic Array

Consider a dynamic array (such as those underlying many programming languages' built-in list types) that starts empty and grows by doubling its capacity whenever it becomes full. A single insertion that triggers a resize requires copying every existing element into the new, larger array — an expensive O(n) operation. Yet intuitively, this expensive resize happens rarely enough that the average cost per insertion should be small. Amortized analysis makes this intuition mathematically precise.

The Aggregate Method: Total Cost Divided by Operation Count

The Aggregate Method computes the total worst-case cost of a sequence of n operations, then divides by n to obtain the amortized cost per operation.

For the dynamic array doubling from size 1:
Resizes happen at insertions 1, 2, 4, 8, 16, ..., 2^k

Cost of insertion i (ignoring the O(1) insertion itself):
0 if i is not a power of 2 (no resize needed)
i if i is a power of 2 (must copy i elements during resize)

Total cost of n insertions:
n · O(1)  (for the n ordinary insertions)
+ Σ (j=0 to log n) 2^j   (for the resize copies)
= n + (2^(⌊log n⌋+1) - 1)
< n + 2n = 3n

Amortized cost per operation: 3n / n = O(1)

Despite individual insertions occasionally costing Θ(n), the amortized cost per insertion across any sequence of n insertions is O(1) — a guarantee that holds for every possible sequence, not merely on average across random inputs.

The Accounting Method: Prepaying for Future Expensive Operations

The Accounting Method assigns each operation an Amortized Cost, which may differ from its actual cost. Cheap operations are charged slightly more than their actual cost, building up a "credit" balance, while expensive operations draw down this stored credit to cover their actual higher cost. The key requirement is that the total credit balance must never go negative at any point in the sequence.

For the dynamic array, assign each insertion
an amortized cost of 3 (even though the actual
cost is usually just 1):

1 unit pays for the insertion itself
2 units are saved as credit

When a resize occurs at size n (doubling from n to 2n),
the resize must copy n elements. But exactly n elements
were inserted since the last resize (when the array grew
from n/2 to n), each having saved 2 credits, providing
2n credits total — comfortably covering the n-element copy cost

Since every operation is charged a constant amortized cost of 3, and the accumulated credit is proven never to run out before it's needed, this confirms the same O(1) amortized bound found by the aggregate method, but through a different and often more intuitive argument.

The Potential Method: A Physical Energy Analogy

The Potential Method defines a Potential Function Φ mapping the data structure's current state to a non-negative real number, conceptually representing "stored energy" that can be drawn upon to pay for future expensive operations.

Amortized cost of operation i:
ĉᵢ = cᵢ + Φ(Dᵢ) - Φ(Dᵢ₋₁)

where cᵢ is the actual cost, Dᵢ is the data structure's
state after operation i, and Φ(D₀) = 0 (initial potential)

For the dynamic array, a natural potential function is Φ(D) = 2 · (number of elements) - (array capacity), which stays at zero right after a resize and grows as more elements are inserted, representing the "banked" work being saved up for the next resize.

For an ordinary insertion (no resize):
actual cost cᵢ = 1
potential increases by 2 (one new element, formula above)
ĉᵢ = 1 + 2 = 3

For an insertion that triggers a resize from n to 2n:
actual cost cᵢ = n + 1 (copy n elements, plus the new insertion)
potential before resize: 2n - n = n
potential after resize: 2(n+1) - 2n = 2
ĉᵢ = (n+1) + (2 - n) = 3

Remarkably, every single operation, whether ordinary or triggering a resize, has the exact same amortized cost of 3 under this potential function, confirming the O(1) amortized bound with mathematical precision, and explaining exactly why the cost stays constant: the potential function precisely tracks the "debt" that gets paid off during expensive operations.

A Second Example: The Binary Counter

Consider a binary counter implemented as an array of bits, incremented by flipping bits from the lowest position, cascading carries as needed. A single increment can flip many bits if there is a long carry chain (such as incrementing 0111 to 1000, flipping all four bits), suggesting a worst-case cost of Θ(k) per increment for a k-bit counter.

Using the potential method, define Φ(D) =
the number of 1-bits currently in the counter

For an increment that flips t bits from 1 to 0
and exactly one bit from 0 to 1:
actual cost cᵢ = t + 1
potential change: -t + 1 (t ones become zeros, one zero becomes one)
ĉᵢ = (t + 1) + (-t + 1) = 2

This shows the amortized cost per increment is a constant O(1), regardless of how long any individual carry chain happens to be, since the potential function's decrease exactly cancels out the cost of flipping the carried-over 1-bits.

Choosing Among the Three Methods

Aggregate Method:
  - Simplest to apply, but only proves the average cost
  - Cannot assign different amortized costs to different operation types

Accounting Method:
  - More flexible; can assign different amortized costs per operation type
  - Requires an intuitive "credit" argument, sometimes harder to construct

Potential Method:
  - Most mathematically rigorous and general
  - Requires finding an appropriate potential function,
    which can require insight but generalizes most cleanly
    to complex data structures

All three methods, when applied correctly, prove the exact same amortized bound — they are different lenses for viewing the same underlying mathematical truth, and the choice between them is typically a matter of which argument is easiest to construct for a given problem.

Why Amortized Analysis Matters Throughout Computer Science

Amortized analysis explains the practical efficiency of many widely used data structures whose worst-case single-operation cost looks alarming in isolation but whose cost per operation, averaged over any realistic sequence of uses, is excellent. Dynamic arrays, hash table resizing (extending the hash tables discussed earlier in this series), and certain advanced tree and heap structures all rely on amortized analysis to rigorously justify their practical efficiency, making this technique an essential tool for evaluating any data structure whose costs vary significantly between individual operations.