Case Study: Table Doubling and Union-Find

Where the rung has brought us

You arrive here already armed. The first guide showed why charging every operation its personal worst case overcounts — a costly step is often paid for by the cheap steps that had to happen first, so the worst case of one operation is the wrong unit when operations come in sequences. The next three guides gave you three honest ways to spread that cost out: the aggregate method (bound the whole sequence, then divide), the accounting method (overcharge cheap operations and save the surplus as credit), and the potential method (define a savings account Phi of the data structure's state, and let differences in Phi pay for spikes). This last guide spends them. We take the two canonical case studies and watch each method settle the same bill, so the methods stop being formulas and become ways of seeing.

Keep the central honesty from the start of the rung in front of you. Amortized O(1) is the average cost over a sequence of operations, not a promise about any single operation. Some appends really do take Theta(n) time; some union-find queries really do walk a long path. Amortized analysis guarantees that such spikes are rare enough that the total, divided by the number of operations, stays small. That is a true and useful guarantee for throughput — but if you need every individual operation to be fast (a real-time deadline, an interactive frame budget), an amortized bound alone will not save you. We will name exactly where that distinction bites.

Table doubling: a growable array that averages O(1) per append

Here is the problem. A fixed array has a fixed capacity, but we want a list we can append to without ever announcing its final size. When the array fills, the only move is to allocate a bigger block and copy everything over. The decision that matters is how much bigger. The winning rule is table doubling: when full, allocate a new array of twice the capacity, copy the old contents, and continue. A single append is usually trivial — write one slot, O(1) — but the append that triggers a resize copies all n current elements, costing Theta(n). Charging that worst case to every append would say each append is Theta(n), so n appends cost Theta(n^2). That is the overcount the rung warned about, and it is wrong. The truth is that n appends cost Theta(n) total, so each is O(1) amortized.

Let the aggregate method prove it the cleanest way: bound the whole sequence, then divide. Start empty and do n appends. The cheap part — one slot-write per append — sums to exactly n. The expensive part is the copies. Resizes happen at sizes 1, 2, 4, 8, ..., up to n, and the copy at capacity 2^k moves 2^k elements. So the total copy work is 1 + 2 + 4 + ... up to n, a geometric sum that is less than 2n. Total work is at most n + 2n = 3n = Theta(n). Divide by n operations: O(1) amortized per append. The geometric series is the whole secret — doubling makes each resize twice as expensive as the last, but also twice as rare, and the rare-but-big terms collapse to a small constant times n.

copy work = 1 + 2 + 4 + ... + n/2 + n
          = sum of 2^k for k=0..log2(n)
          < 2n          (geometric series)
total     = n (writes) + 2n (copies) = Theta(n)
amortized = Theta(n) / n = O(1) per append

The same bill, paid by credits and by potential

Now pay the identical bill with the accounting method, which is often the most intuitive for doubling. Charge each append a flat amortized fee of 3 units. One unit covers the actual slot-write that happens now. The other two units are saved as credit sitting on this freshly added element. Why two? Because when the array next doubles from size m to 2m, each of the m elements must be copied, and we need a unit ready to pay for that copy. Here is the clean bookkeeping: between one resize and the next, the array grows from m to 2m, so m brand-new elements arrive, each carrying 2 saved units — that is 2m units banked. The resize copies 2m elements (the m old plus the m new) at 1 unit each. The 2m banked units exactly cover the 2m copies. The bank never goes negative, so the amortized fee of 3 is valid, and 3 = O(1).

The potential method tells the same story with one number instead of per-element credits. Define a potential Phi that is 0 right after a resize and grows as the array fills, reaching its peak just before the next resize so it can release exactly enough to pay for the copy. A standard choice is Phi = 2 * num_elements - capacity. Check it: just after a resize, the array is half full (num = capacity/2), so Phi = 2*(capacity/2) - capacity = 0. Just before the next resize, the array is full (num = capacity), so Phi = 2*capacity - capacity = capacity, fully charged. A normal append raises num by 1, so Phi rises by 2, and amortized cost = actual 1 + 2 = 3. A resizing append does actual work capacity (the copy) but Phi crashes from capacity back to 0, a drop of capacity, so amortized cost = capacity + 1 - capacity + (small) = O(1). Same constant, derived from a single state function — exactly what choosing Phi well buys you.

A sister example, and one honest scar

The same geometric magic powers the binary counter: increment a k-bit counter n times from zero, and although a single increment can flip every bit (think 0111 -> 1000), the aggregate bill is small. Bit 0 flips every increment (n times), bit 1 every other (n/2), bit 2 every fourth (n/4), and so on — a geometric series summing to less than 2n flips total. So each increment is O(1) amortized, even though the worst single increment is Theta(k). The accounting view is just as crisp: pay 2 units to set a bit (1 to set it now, 1 saved on it to pay for the eventual clear), and clears are then free. It is the exact same accounting trick as table doubling, wearing different clothes.

Now the scar, because it is real. Table doubling's O(1) is amortized, and the worst single append still copies the whole array in Theta(n) time. If those n elements are video frames being appended 60 times a second, the occasional Theta(n) copy is a visible stutter — a frame that misses its deadline — even though the average per append is tiny. Throughput is excellent; worst-case latency is not. Engineers who need bounded per-operation time use a different design (incremental resizing: copy a few old elements on each ordinary append, spreading the work so no single append pays the whole copy). The lesson is exactly the rung's headline honesty: an amortized bound is a guarantee about a sequence, never a per-operation promise.

Union-find: when amortized goes almost-constant

The second case study is grander. A disjoint-set (union-find) structure maintains a partition of items into groups and supports two operations: find(x) returns a representative for x's group, and union(x, y) merges two groups. The standard implementation is a forest: each item points to a parent, and the root of a tree is the representative. Naively, find walks parent pointers up to the root, and a careless union can build a long chain that makes find slow — Theta(n) in the worst case. Two small heuristics together fix this dramatically. First, union by rank: when merging, hang the shorter tree under the taller one (rank approximates height), which keeps trees shallow. Second, path compression: every time find walks from x up to the root, point every node it passed directly at the root, so future finds on those nodes are instant.

1. find(x): walk parent pointers from x up to the root r; that is the representative.
2. Path compression: on the way back, re-point x and every node passed to point directly at r, flattening the tree.
3. union(x, y): find both roots; if different, attach the lower-rank root under the higher-rank root (union by rank).
4. On a rank tie, pick either root as the new parent and increment its rank by one.

What does the amortized analysis deliver? With union by rank alone, every operation is O(log n). With path compression alone, also good. With both together, a celebrated and difficult theorem (due to Tarjan) shows that a sequence of m operations on n items takes O(m * alpha(n)) total time, where alpha is the inverse Ackermann function. The honest, precise statement is this: alpha(n) grows so slowly that for every n that could be written down in this universe it is at most 4 or 5. So the amortized cost per operation is not literally O(1) — alpha(n) does technically grow — but it is so close to constant that no realistic input ever feels the difference. This is the most famous "effectively constant" bound in all of algorithms, and getting it required combining the heuristics; neither alone reaches it.

Two cautions, and what amortized analysis is not

First caution: do not confuse amortized cost with average-case cost. Average-case time depends on an assumed input distribution — it answers "how fast on a random input?" and changes if your inputs are not random. Amortized cost assumes nothing about the input distribution; it is a worst-case guarantee on the total over any sequence, then divided by the count. The table-doubling and union-find bounds hold for adversarial inputs, the worst the world can hand you, with no probability anywhere. That is a strictly stronger kind of promise than average-case, and the two coincide only by accident. Keep them in separate mental boxes.

Second caution: amortized bounds describe scaling, and Big-O still hides constants. The 3-units-per-append fee and the small alpha(n) are genuine, but on a real machine the constant hidden in O(1) — cache behavior, allocator cost, pointer chasing — decides which structure wins at a given size. For small n a plain over-allocated array beats anything fancy; union-find's heuristics only earn their keep once n and m are large. As ever, asymptotics tell you how cost grows, not who wins at n = 50. Measure when it matters.

Step back and see the unity. Table doubling, the binary counter, and union-find look like three unrelated tricks, but each is the rung's single idea in disguise: an occasional expensive operation, paid for in advance by the many cheap operations around it, so that the amortized cost over the whole sequence stays small. The geometric series did it for doubling and the counter; a deep tree-flattening argument did it for union-find. And every one of these results can be read through all three lenses — aggregate, accounting, potential — because they are not three theories but three honest ways of accounting for the very same real cost.