Chapter 16 · Randomized, Amortized, Streaming
Amortized Analysis: the Doubling Array
A single append can copy the whole array, yet n appends cost less than 3n in total. See the spikes, the running average that stays flat, the coins that prepay the copies, and why growing by "+k" instead of "×2" breaks everything.
View:
Compare growth policies on a big run
Cost = element writes + element copies, starting from capacity 1. "Wasted" = the largest fraction of allocated slots that sat empty.
How to read this
- Array (top): each box is one slot of the current allocation. Filled boxes hold elements; empty ones are spare capacity. During a grow, gray boxes are elements still waiting to be copied into the new array and red ones were just copied.
- Cost per append (middle): one bar per append. Most bars are 1 (one write); a spike means a grow that copied every element. The orange line is the running average (total ÷ appends so far); the dashed line is the amortized bound 3.
- Total cost (bottom): the cumulative cost against the 3n line. For doubling it stays below the line forever. For "+k" it bends upward like n²/(2k).
- Accounting view: every append pays the fixed charge. One coin pays the write; copies are paid from coins already parked (or, if those run out, from this append's own charge); leftover coins are parked as gold coins on elements (one on itself, one on its "buddy" in the older half) or in the pool. A copy spends one coin. If the balance ever goes negative, the charge was too low.
- Potential view: Φ = (r·size − capacity)/(r − 1) for growth factor r (so Φ = 2·size − capacity when doubling). The purple dots are the amortized cost ĉ = actual + ΔΦ: flat at 1 + r/(r − 1), which is 3 for doubling and 4 for × 1.5 (small bumps there come from rounding ⌊1.5 · capacity⌋).
Try this
- Doubling, n = 9: grows happen at appends 2, 3, 5 and 9, copying 1, 2, 4 and 8 elements. Total = 9 writes + 15 copies = 24 ≤ 27 = 3·9.
- Slide n to 17: append 17 costs 17 by itself, yet the running average stays under 3. Amortized ≠ "every operation is cheap".
- Accounting view with charge 3: the balance never goes negative for doubling. Now set the charge to 2: find the first append where the pool goes into debt.
- Switch to × 1.5 with charge 3: it goes into debt. What charge keeps it solvent? Theory says 1 + r/(r − 1) = 4 for r = 1.5.
- Switch to + k with k = 4 and n = 64. The spikes keep coming every 4 appends and grow taller; no fixed charge survives. In the comparison, raise n and watch "+k" cost per append grow while × 2 stays below 3.