Amortized Analysis

An amortized bound is a guarantee on the average cost per operation over the worst-case sequence of n operations, even though individual operations may vary wildly in cost. Formally, if a sequence of operations $op_1, op_2, \ldots, op_n$ has true costs $c_1, \ldots, c_n$, an amortized analysis produces amortized costs $\hat{c}_1, \ldots, \hat{c}_n$ such that for every n and every sequence of operations,

If each $\hat{c}_i = O(1)$, we say the data structure supports the operation in amortized constant time, meaning any sequence of n operations costs O(n) total — never O(n²), no matter how the adversary interleaves cheap and expensive calls. This is fundamentally different from average-case analysis. Average-case analysis assumes a probability distribution over inputs (e.g., "assume all n! orderings are equally likely") and bounds the expected cost. Amortized analysis makes no probabilistic assumption whatsoever — it is a deterministic worst-case statement about sequences, proved by accounting rather than probability. A data structure with amortized O(1) operations can have some individual operations that cost Θ(n); the guarantee is only that such expensive operations cannot happen often enough, relative to cheap ones, to blow up the total. Three techniques prove amortized bounds, in increasing order of generality and rigor: 1. Aggregate method — directly compute the total cost $T(n)$ of the worst-case sequence of n operations, then set $\hat{c}_i = T(n)/n$ for all i. Simple, but assigns the same amortized cost to every operation regardless of type, and requires a global argument. 2. Accounting (banker's) method — assign each operation type a fixed amortized charge. When the charge exceeds the true cost, the surplus is stored as credit on specific objects in the structure; when true cost exceeds the charge, the deficit is paid using stored credit. The invariant "credit never goes negative" must hold at all times. 3. Potential method — define a potential function Φ mapping data-structure states to non-negative reals, with Φ(initial) = 0 (or a known baseline). The amortized cost of operation i is $\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$. This is the most flexible and the standard tool for advanced structures, because Φ need not correspond to physical "credit on objects" — it can be any potential-energy-like function of the whole structure. All three methods must yield a valid upper bound on true total cost; the choice among them is a matter of which is easiest to construct and verify for a given structure.

Running example 1: dynamic-array doubling

A dynamic array starts with capacity 1. On `push`, if the array is full, allocate a new array of double the capacity, copy all existing elements over, then insert the new element. This is the strategy behind `std::vector` and Java's `ArrayList`. ``` DynamicArray: capacity = 1 size = 0 A = new array of length capacity PUSH(x): if size == capacity: capacity = 2 * capacity A' = new array of length capacity for i = 0 to size - 1: A'[i] = A[i] // copy: costs Θ(size) A = A' A[size] = x size = size + 1 ``` A single `push` that triggers a resize costs Θ(n) (copying n elements). If resizes always happened, n pushes would cost Θ(n²). But resizes are geometrically rare: they occur only when size is a power of 2 (1, 2, 4, 8, ...), so among n pushes there are only $\lfloor \log_2 n \rfloor + 1$ resizes, and their costs form a geometric series $1 + 2 + 4 + \cdots + n \le 2n$. Total cost is Θ(n), giving amortized O(1) per push — proved rigorously below by all three methods.

Running example 2: stack with multipop

A stack supports `push` (O(1)), `pop` (O(1)), and `multipop(k)`, which pops min(k, current size) elements in one call, costing O(min(k, size)). ``` MULTIPOP(S, k): while not S.empty() and k > 0: S.pop() k = k - 1 ``` A single `multipop(k)` can cost Θ(n) if the stack has n elements. But an element can only be popped once after it is pushed — so across any sequence of n push/pop/multipop operations, the total number of pop operations (whether from `pop` or `multipop`) cannot exceed the total number of pushes, which is at most n. Hence total cost across n operations is O(n), giving amortized O(1) per operation.

Aggregate method applied

Dynamic array. Let $n$ pushes occur, starting from capacity 1. A resize happens when inserting the $(2^j + 1)$-th element for $j = 0, 1, 2, \ldots$, and the copy at that point moves $2^j$ elements. The total cost of all resizes over n pushes is at most

Adding the n unit-cost insertions themselves, total cost $T(n) \le 2n + n = 3n$. Amortized cost per push is $T(n)/n \le 3 = O(1)$.

Multipop. Each element, once pushed, can be popped at most once (by `pop` or by `multipop`). Over n operations there are at most n pushes, hence at most n total pop-steps across all `multipop` and `pop` calls combined. Total cost $T(n) \le n\ (\text{pushes}) + n\ (\text{pop-steps}) = 2n = O(n)$, so amortized cost per operation is O(1).

Accounting method applied

Dynamic array. Charge each `push` an amortized cost of $\hat{c} = 3$ (three "coins"), regardless of whether it triggers a resize.

• 1 coin pays for inserting the new element itself.
• 2 coins are stored as credit on the new element.

Invariant: immediately after any push that does not trigger a resize, every element currently in the second half of the array (i.e., every element inserted since the last resize) carries exactly 2 coins of credit. When the array becomes full and the next push triggers a resize from capacity C to 2C, there are C elements in the array, and the C elements inserted since the previous resize (in fact all of them, since the whole array was filled by them) each carry 2 coins — a total of $2C \ge C$ coins available, exactly enough to pay the Θ(C) copying cost. The credit is spent to zero, and the process restarts identically after the resize. Credit is never negative, so the accounting is valid, and the amortized charge of 3 per push is an honest upper bound.

Multipop. Charge each `push` an amortized cost of 2: 1 coin pays for the push itself, 1 coin is stored as credit on the pushed element. Charge `pop` and each pop-step inside `multipop` an amortized cost of 0 — the actual unit cost of popping an element is paid entirely by spending the 1 credit stored on it when it was pushed. Since every element has exactly 1 credit when pushed and every pop of that element spends exactly 1 credit, credit never goes negative. Total amortized cost over n operations is at most $2n = O(n)$.

Potential method applied

Dynamic array. Define the potential

Check $\Phi \ge 0$ whenever the array is at least half full (true just after any resize, and size only grows relative to a fixed capacity between resizes, so $\Phi \geq 0$ is maintained as an invariant we verify below), and $\Phi = 0$ right after a resize (since size = capacity/2 just after doubling makes $2\cdot(C/2) - C = 0$... more precisely we track it through the push itself). Case 1 — push without resize (size < capacity before push): true cost $c_i = 1$.

Amortized cost $\hat c_i = c_i + \Delta\Phi = 1 + 2 = 3$. Case 2 — push with resize (size = capacity before push): true cost $c_i = \text{size} + 1$ (copy size elements, then insert). Before the push, $\Phi = 2\,\text{size} - \text{capacity} = 2\,\text{size} - \text{size} = \text{size}$ (since capacity = size here). After the push, new capacity $= 2\,\text{size}$, new size $= \text{size}+1$, so

Both cases give amortized cost exactly 3 = O(1), matching the accounting method exactly (the potential Φ is precisely twice the "credit" stored in the accounting proof). Since $\Phi \ge 0$ always and $\Phi_0 = 0$ initially, $\sum \hat c_i \ge \sum c_i$, so total true cost is $O(n)$.

Multipop. Define $\Phi(D) = \text{size}(D)$, the number of elements currently on the stack. For `push`: $c_i = 1$, $\Delta\Phi = 1$, so $\hat c_i = 2$. For `multipop(k)` that pops $k' = \min(k, \text{size})$ elements: $c_i = k'$, $\Delta\Phi = -k'$, so $\hat c_i = k' - k' = 0$. In both cases $\hat c_i = O(1)$, and since $\Phi \ge 0$ always, total true cost over n operations is $O(n)$. ``` // General template for potential-method proofs DEFINE potential function Φ(D) ≥ 0 for all reachable states D VERIFY Φ(D_0) = 0 (or a known constant) FOR each operation i with true cost c_i, transforming D_{i-1} to D_i: ĉ_i = c_i + Φ(D_i) - Φ(D_{i-1}) SHOW ĉ_i = O(f(n)) using the definitions of c_i and Φ CONCLUDE: Σ c_i ≤ Σ ĉ_i - Φ(D_n) + Φ(D_0) ≤ Σ ĉ_i = O(n · f(n)) ```

Time complexity — dynamic array. Any sequence of n `push` operations runs in O(n) total time, i.e., amortized O(1) per push, by any of the three methods above. The bound is tight in the sense that Θ(n) total work is unavoidable (each element must be written at least once), and it is achieved because the geometric-doubling strategy makes resize costs form a convergent geometric sum ($1+2+4+\cdots+n < 2n$) rather than an arithmetic one. This is precisely why doubling is used instead of, say, incrementing capacity by a fixed constant c: with additive growth, resizes happen every c pushes and each costs Θ(current size), giving total cost $\Theta(n^2/c)$ — genuinely quadratic, not amortized constant. Geometric growth is essential, not incidental.

Time complexity — multipop. Any sequence of n stack operations (`push`, `pop`, `multipop`) runs in O(n) total time, amortized O(1) per operation. The key invariant is the conservation of pops: the number of successful pop-steps (via `pop` or inside `multipop`) across the whole sequence cannot exceed the number of prior pushes, because an element must be pushed before it can be popped, and each element is popped at most once. This is the combinatorial fact underlying all three proofs above.

Correctness of the accounting method in general. The method is valid whenever one exhibits (a) an amortized charge $\hat c_i$ per operation, and (b) a credit-invariant showing the running "bank balance" $B_i = \sum_{j\le i}(\hat c_j - c_j)$ never goes negative. If $B_i \ge 0$ for all i, then $\sum_{j \le i} c_j \le \sum_{j \le i} \hat c_j$ for all i — the defining property of a valid amortized bound. The proof obligation is exactly maintaining the credit invariant under every operation type, which is what the "2 coins per new element" argument does for the dynamic array.

Correctness of the potential method in general. Telescoping the definition $\hat c_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$ over $i = 1, \ldots, n$ gives

Rearranging,

provided $\Phi(D_n) \ge \Phi(D_0)$ — which is guaranteed if $\Phi(D_0) = 0$ (or minimal) and $\Phi \ge 0$ always. This telescoping argument is the entire proof; the only work is defining a Φ under which each individual $\hat c_i$ is small. The accounting method's "credit" is exactly $\Phi$ in disguise (credit-per-element summed equals Φ in the dynamic-array example: $\Phi = 2\,\text{size} - \text{capacity}$ equals total stored credit).

Honest tradeoffs. Amortized bounds guarantee total sequence cost, not per-call latency: a single call can still take Θ(n) time in the worst case (a resize, or a multipop of the whole stack). This matters in real-time or latency-sensitive systems — a game engine that cannot tolerate an occasional 5 ms stall from a vector resize may need a data structure with genuine worst-case O(1) operations (e.g., incremental/lazy resizing schemes), not merely amortized ones. Amortized analysis also says nothing under adversarial cancellation attacks against a shared, mutable structure used concurrently — the credit/potential argument assumes a single sequential thread of operations; concurrent access requires separate reasoning.

Trace a dynamic array starting empty (capacity 1) through 10 pushes, then two multipops, tracking true cost, potential $\Phi = 2\cdot\text{size} - \text{capacity}$, and amortized cost $\hat c = c + \Delta\Phi$.

Sum of true costs: $1+2+3+1+5+1+1+1+9+1 = 25$. Sum of amortized costs: $2+3+3+3+3+3+3+3+3+3 = 29$. Indeed $25 \le 29$, and $29/10 = 2.9 \approx 3$ per push as the theory predicts (the first push is slightly cheaper because $\Phi(D_0)=0$ exactly and capacity starts already at 1, a minor boundary effect). Now apply `multipop(4)` to the 10-element stack (size 10, capacity 16), popping elements 10, 9, 8, 7 (LIFO order):

Using $\Phi = \text{size}$ for the stack-credit view (not the array-capacity view — multipop's potential is defined purely on stack size, since here we assume the underlying array need not shrink): $c = 4$ (four real pops), $\Delta\Phi = 6 - 10 = -4$, so $\hat c = 4 + (-4) = 0$. The four credits banked during pushes 7–10 (one credit per pushed element, per the accounting-method construction) exactly pay for the four pops — no new charge is levied. A second `multipop(20)` on the now-6-element stack pops all 6 remaining elements: $c = 6$, $\Delta\Phi = 0 - 6 = -6$, $\hat c = 0$ again. Every multipop, however large, has amortized cost 0, confirming the earlier general argument.

Amortized analysis crystallized as a named technique in the study of self-adjusting data structures in the 1980s, though the underlying accounting intuition — "some operations prepay for future ones" — appears implicitly in earlier data-structure analyses (e.g., binary counters and union-find). The potential-method formalization is most closely associated with Robert Tarjan, who used it to analyze splay trees, Fibonacci heaps, and path compression in union-find, turning ad hoc credit arguments into a systematic, reusable mathematical framework.

Every mainstream dynamic-array implementation — C++ `std::vector`, Java `ArrayList`, Python `list`, Go slices, Rust `Vec` — relies on geometric-growth resizing precisely because it delivers amortized O(1) `push_back`/`append`, making these structures practical defaults for general-purpose programming rather than niche tools. Hash tables built on dynamic arrays (essentially every language's built-in hash map or dictionary) use the identical doubling argument to justify amortized O(1) insertion despite occasional full-table rehashes. Stack-based algorithms that use multipop-like batching — for instance the classic "largest rectangle in histogram" algorithm, or bracket-matching parsers that pop multiple unmatched symbols at once — rely on exactly the conservation-of-pops argument to claim overall linear time. Text editors and version-control systems that maintain undo/redo stacks with batch-clearing operations use the same reasoning. The potential-method machinery introduced here is also the direct prerequisite for analyzing more advanced amortized structures: splay trees, Fibonacci heaps, and — foreshadowing a natural next topic — Disjoint-Set Union-Find, where path compression and union-by-rank combine to give a nearly-constant (inverse-Ackermann) amortized cost per operation, one of the most celebrated results in data-structure analysis. Understanding amortized analysis is also foundational for reasoning about Big-O Notation claims that appear in library documentation, and it builds directly on intuition from Arrays and Dynamic Arrays.

Ask the tutor: How does the potential-method proof change when a Fibonacci heap's decrease-key operation is added to the mix, and why does that require a more elaborate potential function than the dynamic array's?