Amortized Analysis: The Aggregate Method

Amortized analysis answers a question that per-operation worst-case analysis cannot: how expensive is a data structure operation when performed repeatedly, accounting for the fact that expensive operations restore conditions that make many subsequent operations cheap? A single worst-case bound applied to every operation in a sequence of $n$ operations, then multiplied by $n$, is always a valid upper bound on total cost — but it can be wildly loose if expensive operations cannot actually happen often. Amortized analysis produces a tighter, still fully rigorous, bound on the total cost of any sequence, expressed as an amortized cost per operation. The aggregate method is the most direct of the three standard techniques for amortized analysis (the others being the accounting method and the potential method, which generalize this idea to assign different costs to different operation types). Given a sequence of $n$ operations $op_1, op_2, \ldots, op_n$ applied to a data structure starting from a fixed initial state (usually empty), let $T(n)$ denote the true worst-case total cost of any such sequence of length $n$. The amortized cost per operation is then defined as

Crucially, this single amortized cost $\hat c$ is applied uniformly to every operation in the sequence, regardless of that operation's individual actual cost. The guarantee delivered is: for any sequence of $n$ operations, the total actual cost is at most $n \cdot \hat c$. This is a worst-case guarantee over sequences — no assumption of randomness, no average over an input distribution — which is exactly why amortized bounds remain valid even under adversarial usage patterns, a property essential in systems where an adversary (or unlucky user traffic pattern) could otherwise engineer a sequence to repeatedly trigger the worst case. It is important to be precise about what the aggregate method does not claim. It does not claim that every operation costs $\hat c$; some cost far less, some (rarely) cost far more. It does not use probability at all, distinguishing it from average-case analysis via Best, Average, and Worst Case Analysis, which typically assumes a distribution over inputs and computes an expectation. Amortized analysis instead exploits structural facts: that an expensive operation leaves the structure in a state where cheap operations must follow, so expensive operations cannot cluster arbitrarily. The aggregate method proves this by computing $T(n)$ directly — usually via a summation, a potential telescoping argument, or a clever accounting of "credits" spent — rather than by reasoning operation-by-operation.

The aggregate method proceeds in three explicit steps, applied to a fixed sequence length $n$ of operations on an initially empty (or fixed-start) structure.

Step 1 — Identify the true worst-case total cost $T(n)$. Do not bound each operation separately and sum the bounds; that gives a valid but often loose bound. Instead, analyze the entire sequence together, exploiting the fact that expensive operations (like a resize) change the state in a way that constrains how soon the next expensive operation can occur.

Step 2 — Compute or bound $T(n)$ using a direct sum, often a geometric or arithmetic series. This is the technical heart of the method. For structures whose expensive operation triggers periodically (every $k$-th operation, or whenever a counter overflows), $T(n)$ decomposes into a sum over "cheap" operations plus a sum over "expensive" operations, and the expensive sum telescopes or collapses via a geometric series identity.

Step 3 — Divide by $n$ to get the amortized cost, and state the theorem precisely. The final claim is always of the form: "any sequence of $n$ operations on this structure costs at most $O(f(n))$ in total, hence $O(f(n)/n)$ amortized per operation." State both forms — the aggregate bound and the per-operation bound — since the aggregate bound is what you actually proved, and the per-operation bound is the more usable design fact. Below is the technique made concrete on the two canonical examples: the dynamic array (`push_back` with doubling) and the binary counter (incrementing). ``` // DYNAMIC ARRAY WITH DOUBLING // State: array A with capacity cap, current size n // Operation: PUSH(x) appends x to the array procedure PUSH(x): if n == cap: allocate new array A' of capacity 2 cap // cost: cap (copy all elements) copy all n elements from A into A' A <- A' cap <- 2 cap A[n] <- x n <- n + 1 // cost of this call: 1 (for the assignment) plus cap if a resize occurred // AGGREGATE ANALYSIS over a sequence of n PUSH operations starting from empty, cap = 1: // // Resizes occur at pushes number 1, 2, 4, 8, 16, ..., i.e. when n reaches a power of two. // At the resize triggered when the array holds 2^i elements, the copy cost is 2^i. // // T(n) = (cost of all n unit assignments) + (cost of all resize copies) // = n + (1 + 2 + 4 + 8 + ... + 2^(floor(log2 n))) // = n + (2^(floor(log2 n) + 1) - 1) // <= n + (2n - 1) [geometric series bound: 2^(floor(log2 n)+1) <= 2n] // = 3n - 1 // // Hence T(n) = O(n), and amortized cost per PUSH = T(n) / n = O(1). ``` ``` // BINARY COUNTER INCREMENT // State: array of bits A[0..k-1], representing a k-bit binary counter, initially all 0 // Operation: INCREMENT flips bits starting from the lowest-order bit procedure INCREMENT(A): i <- 0 while i < length(A) and A[i] == 1: A[i] <- 0 // cost: 1 bit flip (a "reset") i <- i + 1 if i < length(A): A[i] <- 1 // cost: 1 bit flip (a "set") // AGGREGATE ANALYSIS over a sequence of n INCREMENT operations starting from A = 0: // // Cost of one INCREMENT = number of bits flipped = (number of trailing 1s reset) + 1. // Total cost T(n) = sum over all n increments of (bits flipped). // // Key structural fact: bit A[j] flips from 0 to 1 (a "set") exactly once every 2^j increments, // and every flip of A[j] to 1 is later matched by at most one flip back to 0 before it can flip // to 1 again. So over n increments, bit A[j] flips at most floor(n / 2^j) + 1 times total. // // T(n) = sum_{j=0}^{floor(log2 n)} ( floor(n / 2^j) + 1 ) // <= sum_{j=0}^{floor(log2 n)} ( n / 2^j + 1 ) // <= n * sum_{j=0}^{inf} (1/2^j) + O(log n) // = 2n + O(log n) // = O(n) // // Hence amortized cost per INCREMENT = T(n) / n = O(1). ``` The pattern in both examples is identical: identify which "bit" of work each operation touches (an array slot copied during resize, a bit flipped during increment), bound how many times in total, across the whole sequence, that unit of work can occur, sum those bounds (usually a geometric series that telescopes to $O(n)$), and divide by $n$.

Dynamic array claim. For any sequence of $n$ `PUSH` operations on an initially empty dynamic array starting at capacity $1$ and doubling on overflow, the total cost is $T(n) = O(n)$, hence the amortized cost per `PUSH` is $O(1)$. Proof. Split the total cost into two parts: (a) the cost of the constant-time array-slot writes, one per push, contributing exactly $n$; and (b) the cost of copying during resizes. A resize copying $m$ elements occurs only when the array is full at size $m$ and $m$ is a power of two (with the convention that the structure starts at capacity $1$), so the sizes at which resizes occur are $1, 2, 4, 8, \ldots$ up to at most $n$. The total copy cost is thus at most

This is a finite geometric series, and the standard identity $\sum_{i=0}^{k} 2^i = 2^{k+1}-1$ gives the bound directly, with $2^{\lfloor \log_2 n\rfloor} \le n$ ensuring the sum is under $2n$. Adding the $n$ unit-cost writes,

so $T(n) = O(n)$, and the amortized cost per operation is $T(n)/n = O(1)$. $\blacksquare$ This argument is exact and does not rely on any assumption about which elements are pushed or in what order operations other than `PUSH` occur — it is a genuine worst-case bound over all sequences of $n$ pushes, because resizes are forced to happen at specific, predictable sizes regardless of the data being pushed.

Binary counter claim. For any sequence of $n$ `INCREMENT` operations starting from an all-zero $k$-bit counter, the total number of bit flips is $O(n)$, hence $O(1)$ amortized per increment (independent of $k$, so long as $n$ does not overflow the counter). Proof. Bit $A[j]$ can only be set to $1$ (flip $0 \to 1$) when the low-order counter value is a multiple of $2^j$, which happens at most $\lfloor n/2^j \rfloor + 1$ times over $n$ increments; each such set is followed by at most one reset ($1 \to 0$) before the next set. So the total number of flips of bit $j$ across the sequence is at most $2(\lfloor n/2^j\rfloor + 1)$. Summing over all bits $j = 0, \ldots, \lfloor \log_2 n \rfloor$ (bits beyond this never flip for a counter incremented only $n$ times),

Again the geometric series $\sum 1/2^j = 2$ is the crux: it converges, so the total flip count stays linear in $n$ rather than growing with $k$ or with $n \log n$ (which is what naive per-operation worst-case analysis, $O(\log n)$ flips per increment times $n$ increments, would suggest). $\blacksquare$

Honesty about what is and is not proven. The aggregate method proves a bound on the sum of costs over a sequence; it says nothing about the cost of an individual operation in isolation, and in particular it never claims that a single "expensive" operation is somehow secretly cheap — one increment really can flip $\Theta(\log n)$ bits, one push really can trigger an $\Omega(n)$-time copy. What amortized analysis guarantees is that such expensive operations are rare enough, and correlated tightly enough with recent cheap operations, that the running total stays linear. This is a genuinely different (and often more useful) claim than either worst-case-per-operation analysis or average-case analysis over random inputs, since it holds under adversarial sequencing — an adversary choosing exactly when to push or increment cannot force $T(n)$ above $O(n)$, because the structure itself (via doubling capacities, via binary carrying) prevents expensive events from clustering.

A key limitation of the aggregate method is that it produces one amortized cost shared by every operation type in the sequence. If a structure supports several distinct operations with genuinely different amortized costs — for instance a mixture of cheap lookups and occasionally expensive rebalancing insertions where you want separate bounds for each operation type — the aggregate method's single shared $\hat c = T(n)/n$ can be too coarse, or simply awkward to state per operation type. That refinement is exactly the motivation for the accounting method (assigning differing "amortized charges" to different operation types, banking credit) and the potential method (defining a potential function on the structure's state), both of which recover per-operation-type amortized costs while remaining consistent with the aggregate bound.

Trace $T(n)$ explicitly for a dynamic array over $n = 10$ pushes, starting empty with capacity $1$, doubling whenever full.

Summing the "total op cost" column:

Compare this to the naive (and correct, but loose) worst-case-per-operation bound: the worst single push in this sequence costs $9$, so multiplying that worst case by $10$ operations gives an upper bound of $90$ — more than three times the true total of $25$. The aggregate method's actual computation, $T(n) \le 3n$, predicts $T(10) \le 30$, which is a tight and honest bound (the true value $25$ sits comfortably under it), while the naive per-operation bound of $90$ dramatically overstates the true cost because it assumes every operation could be as expensive as the single worst one, which the doubling structure makes impossible. The amortized cost per push in this trace is $25/10 = 2.5$, consistent with the $O(1)$ claim (bounded above by $3$) and nowhere near the $O(n)$ that per-operation worst-case analysis alone would suggest if applied naively across a growing sequence. A second trace, for the binary counter, makes the same point with a different mechanism. Starting from `0000` and performing $n=8$ increments:

Sum of flip counts: $1+2+1+3+1+2+1+4 = 15$. The naive bound (each increment costs up to $k = 4$ bit flips, times $n=8$ increments) gives $32$; the aggregate bound $T(n) \le 4n = 32$ matches this loose bound closely here because $n$ is small relative to $2^k$, but as $n$ grows toward $2^k$ and beyond, the true total continues to track close to $2n$–$4n$ rather than scaling with $k$, exactly as the geometric-series argument predicts — the amortized cost per increment converges to a small constant, not to $\log n$.

The vocabulary and formal apparatus of amortized analysis — the aggregate, accounting (banker's), and potential (physicist's) methods — were crystallized in the early 1980s in the context of analyzing self-adjusting data structures, most famously splay trees and the union-find structure with path compression.

The aggregate method itself predates its formal naming — the doubling-array argument and the binary-counter argument were folklore results used implicitly wherever incremental structures were analyzed — but Tarjan's synthesis gave the field a shared vocabulary and proof template, distinguishing amortized reasoning cleanly from the probabilistic reasoning used in Best, Average, and Worst Case Analysis and connecting it to inductive proof techniques familiar from The Substitution Method.

Dynamic arrays with geometric growth (Python's `list`, Java's `ArrayList`, C++'s `std::vector`) are the textbook application: `append`/`push_back` is documented and relied upon as amortized $O(1)$, which is precisely the aggregate-method result derived above, and every performance-sensitive system that builds up large collections incrementally depends on this guarantee holding. Hash tables that resize (grow their bucket array) when a load-factor threshold is crossed use the identical doubling argument to guarantee amortized $O(1)$ insertion, which underlies the performance model of virtually every hash-based associative container in production language runtimes. Union-find (disjoint-set) structures with path compression and union by rank, used inside Kruskal's minimum spanning tree algorithm, in compiler alias analysis, and in dynamic connectivity queries for network monitoring, rely on amortized analysis (via a more refined argument than pure aggregate counting) to justify their near-linear total running time across a sequence of unions and finds. Splay trees, used in some caching layers and in certain kernel/scheduler data structures, guarantee amortized $O(\log n)$ per operation even though any single access can take $O(n)$ time in the worst case — the structure's self-adjusting behavior after each access is exactly what the amortized argument accounts for. Incremental algorithms in streaming and online systems — incrementally maintained checksums, incremental topological sort updates, buffer-flushing policies in write-heavy storage engines — are routinely justified with the same style of "total cost over the whole run is linear" argument that the aggregate method formalizes, making it a foundational tool anywhere a system processes a long stream of small updates punctuated by occasional bulk maintenance work.

Ask the tutor: How does the accounting method's "credit invariant" formally guarantee the same total bound the aggregate method proves directly?