Amortized vs. Worst-Case & the Aggregate Method

Some operations are usually cheap but occasionally very expensive. Judging them only by their worst single case is misleading — you'd never do that expensive step often. Amortized analysis measures the cost averaged over a whole sequence of operations, guaranteeing the average holds even in the worst case.

Worst-case (per operation): the maximum cost of one single operation. Pessimistic — assumes the bad case happens every time.

Amortized cost (per operation): the total cost of a sequence of n operations, divided by n. It spreads the cost of rare expensive operations across the many cheap ones.

Key point: amortized analysis is not average-case analysis. Average-case uses probability (what happens on random input). Amortized analysis is a worst-case guarantee over a sequence — no probabilities involved. If the amortized cost of an operation is O(1), then any sequence of n operations costs at most O(n), guaranteed.

There are three standard techniques, covered across this and the next topic:

1. Aggregate method — total cost ÷ number of operations.
2. Accounting (banker's) method — charge each operation a fixed fee; save the surplus as credit.
3. Potential method — track a "stored energy" function of the data structure's state.

The classic illustration is appending to a dynamic array (like C++ std::vector or Python list). The array has a fixed capacity; when it fills up, the next append must:

1. Allocate a new, larger array (usually double the capacity),
2. Copy all existing elements over — an O(n) step,
3. Then store the new element.

Both statements are true at once. A single append can indeed cost O(n) (right when the array is full). But such expensive appends are rare: after doubling from capacity n to 2n, the next n appends are all cheap O(1) — no copy needed. The one expensive step is "paid for" by the run of cheap steps that follow. Averaged out, each append costs a small constant. We prove exactly that below with the aggregate method.

Why is append "amortized O(1)" even though resizing is O(n)? Because resizing does not happen every time — it happens only after the array doubles. To reach n elements you resize at sizes 1, 2, 4, 8, …, n, and the total copying work across all those resizes is only ~2n, i.e. O(n) for n appends → O(1) each on average.

The aggregate method is the most direct technique — no cleverness, just arithmetic:

Aggregate method. Compute the total worst-case cost T(n) of any sequence of n operations. Then the amortized cost per operation is T(n) / n. Every operation is assigned the same amortized cost, regardless of its individual type.

In plain words: add up the cost of everything, then divide by how many operations there were. You don't analyze operations one at a time; you bound the whole batch and share the bill equally.

It works best when you can find a clean formula or bound for the total — as with the geometric series of a doubling array.

Append n elements into an initially-empty doubling array. Split each append's cost into two parts:

• Base cost: every append writes 1 element → total n.
• Copy cost: a resize copies all current elements. Resizes happen when the size passes 1, 2, 4, 8, …, up to n. The copies sum to a geometric series:

Now apply the aggregate rule:

So n appends cost O(n) in total, hence O(1) amortized each — even though the worst single append is O(n). The trick is that doubling makes expensive resizes exponentially rare: the last resize (the costliest, copying n/2 elements) happens once, the one before it half as often, and so on — a series that never exceeds 2n.

Reach for amortized analysis whenever a data structure has occasional expensive "rebuild" operations funded by many cheap ones:

• Dynamic arrays / std::vector — resize on growth (this chapter).
• B-trees — occasional node splits and merges among many cheap inserts/deletes.
• Hash tables — occasional rehash when the load factor is exceeded.
• Disjoint-set / union-find — path compression amortizes to near-O(1).
• Incrementing a binary counter — most increments flip one bit; rare ones flip many.

In all of these, the per-operation worst case is scary but unrepresentative. Amortized analysis gives the honest, usable number — and, unlike average-case, it holds for every input sequence, not just typical ones.

For the doubling dynamic array: worst single append = O(n), but amortized append = O(1) by the aggregate method — the number you should actually use when reasoning about performance.