One idea: total first, average second
The previous guide left us with a complaint and a hope. The complaint: multiplying the worst case of a single operation by n badly overcounts, because the expensive operations cannot all happen at once — they have to take turns. The hope: there should be a way to charge each operation a smooth, honest price that still adds up to the true total. The aggregate method is the most direct way to cash in that hope, and it is almost embarrassingly simple. Instead of asking 'what is the worst a single operation can cost?', you ask 'what is the worst a whole sequence of n operations can cost, all together?' — and only then divide by n.
Write that as a recipe. Let T(n) be a tight upper bound on the total cost of any sequence of n operations starting from an empty structure. Then the aggregate method declares the amortized cost per operation to be T(n) divided by n. Notice what is and is not being claimed. Every operation is assigned the same amortized cost, the average T(n)/n. That average is honest in the only sense that matters: if you charge each of the n operations this amount, the charges sum to T(n), which really does bound what the sequence actually costs. No accounting trickery, no per-operation case analysis — just a total, divided.
The binary counter, counted whole
The cleanest first example is incrementing a binary counter, the same structure introduced in the previous guide. You have a k-bit counter, all zeros, and you call increment n times. The cost of one increment is the number of bit flips it performs. A single increment can be cheap — turning ...0 into ...1 flips one bit — or expensive — turning 0111 into 1000 flips four bits as a run of 1s carries all the way up. The naive worst case says each increment can flip up to k bits, so n increments cost O(n k). True, but loose: you cannot flip k bits every single time, because a long carry chain only happens when there is a long run of 1s waiting to be cleared.
The aggregate method refuses to bound increments one at a time. Instead it asks: over the whole run of n increments, how many bit flips happen in total? Reframe by bit position rather than by operation. Bit 0 — the lowest bit — flips on every single increment, so it flips n times. Bit 1 flips half as often, every second increment, so about n/2 times. Bit 2 flips every fourth increment, about n/4 times. In general bit i flips about n divided by 2^i times. The grand total of flips is therefore the sum from i=0 of n/2^i, which is n times the geometric series (1 + 1/2 + 1/4 + ...), and that series is less than 2.
total flips over n increments = (flips of bit 0) + (flips of bit 1) + (flips of bit 2) + ... = n + n/2 + n/4 + n/8 + ... = n * (1 + 1/2 + 1/4 + 1/8 + ...) < n * 2 = 2n amortized cost per increment = total / n < 2n / n = 2 = O(1)
So the true total cost of n increments is less than 2n, not n times k. Divide by n and the amortized cost per increment is less than 2 — a constant, O(1), independent of how wide the counter is. This is the headline result for the amortized binary counter, and notice how the win came from a sum over positions rather than a max over operations. The expensive all-carry increments are real, but they are so rare that the cheap ones pay for them many times over. The geometric series is doing the quiet arithmetic of that fairness.
Multipop: a sequence can only pop what it pushed
The second classic is the stack with multipop, and it teaches a different flavour of the same trick. Start with an ordinary stack supporting push and pop, each costing 1. Now add multipop(s): pop the top min(s, current size) elements in one call. A single multipop can be expensive — if the stack holds a million items, one multipop(s) with a large s can do a million units of work. So the naive per-operation worst case for a sequence of n operations is O(n^2): n operations, each possibly touching up to n elements.
The aggregate method sidesteps that by a conservation argument so simple it feels like cheating. Every element that gets popped — whether by a plain pop or as one victim of a multipop — must have been pushed onto the stack at some earlier moment. An element cannot be popped twice without being pushed again in between. So across the entire sequence, the total number of pop actions (counting each element a multipop removes) can never exceed the total number of pushes. There are at most n push operations in a sequence of n operations, hence at most n pushes' worth of elements, hence at most n pop actions in total.
Add it up: total work = (pushes) + (pop actions) is at most n + n = 2n, so the total over any sequence of n operations is O(n). Divide by n and every operation — push, pop, and even the scary multipop — has amortized cost O(1). The lesson generalizing the binary counter: the aggregate method shines when you can find a global accounting identity (every pop matches an earlier push) that caps the total directly, even though no individual operation has a small worst case. You are not bounding the cost of one multipop; you are bounding how much total popping the whole sequence is physically capable of.
Table doubling: where it works and where it strains
The aggregate method also dispatches the example that motivates this whole rung: appending to a dynamic array that doubles when full. Most appends are O(1) — just write into the next free slot. But when the array fills, the append that triggers a resize must allocate a new array of double the size and copy every existing element, costing Theta(current size). Those copy-heavy appends are the rare spikes. To aggregate, sum the copying work across n appends: resizes happen at sizes 1, 2, 4, 8, ... up to n, and the copies they perform total 1 + 2 + 4 + ... + n, a geometric series that sums to less than 2n.
Now add the cheap part. Each of the n appends also does O(1) base work to write its element, contributing n. So the total is at most n (writes) plus under 2n (copies), which is O(n), and the amortized cost per append is O(1). The same geometric-series magic as the binary counter: doubling makes resizes exponentially rare as the array grows, so the rare big copies, summed, are merely linear. This is the precise reason a growable array can promise amortized O(1) append despite occasional Theta(n) stalls.
What the method is really telling you
Step back and notice the shared shape of all three examples. In each, the naive per-operation worst case (worst case times n) was loose by a real factor — O(n k) versus O(n), O(n^2) versus O(n) — and in each, a single global count of the total dissolved the looseness. For the counter and the array it was a geometric series; for the stack it was a conservation law. The aggregate method does not change the algorithm at all; it changes the bookkeeping, replacing a pessimistic per-step max with an honest whole-sequence sum.
- Fix the sequence: n operations from an empty structure, and decide what 'cost' you are counting (bit flips, element touches, copies).
- Find the total T(n) by a clever global count — sum over positions, or a conservation argument — rather than summing per-operation worst cases.
- Verify T(n) is a true upper bound for the worst sequence, with no hidden probability assumption — it must hold for the most adversarial order of operations.
- Report the amortized cost as T(n)/n, and remember it is one flat average shared by all operations, not a per-operation guarantee.
One last honesty check that keeps amortized reasoning grounded. The amortized cost O(1) here is a statement about scaling of the total, in the same spirit as any asymptotic bound: it hides constants and ignores small n, so for a tiny sequence the resize spikes are a real fraction of the work and 'O(1) amortized' is not a promise that every early append is instant. What it does promise — provably, for the worst case — is that as the sequence grows, the average per operation stays bounded by a constant. That is the whole gift of the aggregate method: from a single total, an honest per-operation price. The next guide keeps the same goal but hands out the bill differently, letting cheap operations prepay for the expensive ones they will later cause.