Visual walkthrough — Array — static, dynamic; cache locality; amortized O(1) append
We will build every idea from zero. By the end you will see why the total work is a shrinking staircase that never adds up to more than about twice the number of items.
Prerequisite ideas we lean on, all linked for you: the parent Array note, Amortized Analysis, Geometric Series, and Big-O Notation.
Step 1 — What "append" actually costs (two different prices)
WHAT. Every dynamic array remembers two numbers (from the parent note):
size— how many elements are actually stored right now.capacity— how many slots the allocated block can hold. Alwayscapacity ≥ size.
WHY two prices. If there is still an empty slot (size < capacity), appending is just "write into the slot and add 1 to size" — one cheap step. But if the block is completely full (size == capacity), there is no wall space left; the computer must build a bigger block and carry everything over.
PICTURE. Below, the blue boxes are used slots, the gray dashed boxes are empty-but-allocated capacity. On the left there is room (cheap append). On the right the block is full, so appending forces a rebuild (expensive append).
Step 2 — When does the expensive case happen? (the resize points)
WHAT. We fix a growth rule: start with capacity 1, and every time the block fills, double the capacity. So capacity marches through the powers of two:
WHY doubling and not, say, +1? This is the whole question of the page, and Step 6 shows the disaster of +1. For now: doubling makes the gaps between resizes get bigger and bigger, which is exactly what will save us.
PICTURE. Think of it as a number line of appends (1st, 2nd, 3rd, …). A resize fires only at the moments the array was already full — at append number 1, 2, 3, 5, 9, 17, … (right when size hits the current capacity). Notice how the red "resize" marks spread apart.
Step 3 — Count the copies at each resize
WHAT. At each resize we copy all current elements into the new block. Let's tabulate exactly how many elements get copied each time.
WHY. The only expensive work in the entire life of the array is these copies. If we can add them all up, we know the total cost — everything else is just cheap single writes.
PICTURE. Each resize is drawn as a bar whose height is "elements copied this time." When capacity goes we copy 1; we copy 2; we copy 4; we copy 8. The bars are the powers of two.
Step 4 — Add up all the copies (the geometric-series punchline)
WHAT. Suppose after growing we have room for elements, so the last resize took capacity up to where is around . Total copies is the sum of all those bars:
WHY this tool — a Geometric Series. Each term is exactly double the one before. A sum where every term multiplies by a fixed factor is a geometric series, and it has a famous closed form. We use it because it turns an ever-growing pile of terms into one clean number, and that number is the answer.
PICTURE. Stack the bars from Step 3 end to end. The magic of doubling: the whole stack of all previous bars is always shorter than the single next bar. So the total can never run away — it's pinned just under twice the last (biggest) bar.
Recall Why is
?
Because in binary, is a 1 followed by zeros, and subtracting 1 turns it into ones: , which is exactly . The sum of all lower powers is always one short of the next power. ::: A doubling sum is always one less than the next doubling.
Step 5 — Divide by the number of appends → amortized O(1)
WHAT. We did cheap writes (one per element) plus copies. Total lifetime work: Spread that over the appends that caused it.
WHY divide. Amortized Analysis asks "if I add up the cost of a long run of operations and share it evenly, what does each one cost?" That shared cost is the amortized cost — the honest average a user experiences over many appends.
PICTURE. Imagine the tall spikes (resizes) being melted down and poured flat across all the appends. The jagged skyline of costs becomes a low, flat line at height .
Step 6 — The degenerate case: growing by +1 (why it fails)
WHAT. Replace "double" with "add one slot each time it's full." Now the array is full after every single append, so every append triggers a copy.
WHY show this. To prove doubling is special, we must see what breaks without it. This is the edge case the parent note warned about — and it's the exact same sum done wrong.
PICTURE. Now the copy-count bars are — they grow linearly, not by doubling. There's no "next bar dwarfs all previous" magic; the bars pile into a big triangle.
The one-picture summary
WHAT. One figure that stacks the whole argument: the two-price append (Step 1), the doubling bars whose sum is capped at (Steps 3–4), and the resulting flat amortized line (Step 5) — versus the +1 triangle disaster (Step 6).
Recall Feynman retelling — the whole walkthrough in plain words
You're filling a shelf. Sometimes adding a book is instant (there's a free spot). Sometimes the shelf is full, so you have to buy a bigger shelf and move every book across — slow. Question: is adding a book fast "on average"?
The trick is how much bigger you make the new shelf. If you always double it, then after a painful move you get a huge stretch of free spots before the next move — and the free stretch grows every time. When you total up all the book-moving you ever do, it comes to less than twice the number of books you own. Twice-the-books, spread over all-the-books, is a fixed little number per book — so on average, adding a book is cheap. That "cheap on average" is what O(1) amortized means.
But if instead you only add one slot at a time, the shelf is full again immediately, so you move everything on every append. That totals a triangle of work — about moves — which averages to per book. Disaster. Moral: always multiply, never just add.