Amortized O(1) operations: Visual walkthrough — Coding deep dive

Before we start, the precondition and the two words we lean on:

Step 1 — The array is a row of boxes, and it can get full

WHAT. Picture the array as a row of boxes. Each box holds one item. The number of boxes is the capacity; the number of filled boxes is the size.

WHY. We need a mental object before any math. "Full" means size = capacity — there is no empty box left, so the next push has nowhere to go.

PICTURE. In the figure, blue boxes are filled, gray boxes are empty. The moment every box turns blue, we are stuck — that is the trigger for everything that follows.

Step 2 — The choice: grow by +1, or double?

WHAT. When full, we must make a bigger array and pour the old items into it. Two strategies:

+1 growth: make exactly one extra box each time.
doubling: make twice as many boxes.

WHY. This single choice decides whether the whole structure is fast or slow. We compare them side by side so the difference is visual, not abstract.

PICTURE. Top row: +1 growth — the array creeps up 1,2,3,4,5,... and it is full again immediately, so it copies again immediately. Bottom row: doubling — capacities jump 1,2,4,8,... leaving lots of free boxes (gray) after each resize, so the next resize is far away.

Step 3 — Count the cheap part: every item is written exactly once

WHAT. Ignore resizing for a moment. Push $n$ items. Each push, at minimum, writes its one item into a slot.

WHY. This cost is unavoidable and simple, so we bank it first before tackling the tricky copies. Getting the easy term out of the way keeps the bookkeeping clean.

PICTURE. $n$ blue boxes light up, one per push. The counter on the side ticks $1, 2, 3, \dots, n$ .

$total ink for new items write cost = one write per push n$

$n$ = how many items we pushed.
"one write per push" = the size grows by exactly 1 each push, so we do exactly $n$ writes over the whole run.

Step 4 — Count the expensive part: copies happen at powers of two

WHAT. With doubling from capacity 1, the array becomes full exactly when its size hits $1, 2, 4, 8, \dots$ — the powers of two. At each of those moments we resize and copy everything currently inside.

WHY. We want to know how many copies pile up. Doubling means a resize at size $2^{k}$ copies $2^{k}$ items — so the copy amounts are themselves $1, 2, 4, 8, \dots$ .

PICTURE. A staircase: each resize is an orange bar whose height is the number of items copied. The bars are $1, 2, 4, 8$ — each twice the one before.

$copy cost = one orange bar per resize 1 + 2 + 4 + \dots + 2^{m}$

$2^{m}$ = the last and largest resize that happens before we finish, and by the definition above $2^{m} \leq n$ .
each term = the whole array getting copied once, at ever-larger sizes.

Step 5 — The magic: that sum is less than twice the last bar

WHAT. We add up the orange bars $1 + 2 + 4 + \dots + 2^{m}$ . The result is exactly $2^{m + 1} - 1$ , which is less than $2 \cdot 2^{m}$ .

WHY (this is the heart). Why does a growing sum stay small? Because each bar is double the previous one, so all the earlier bars stacked together are still shorter than the last bar. This is a Geometric Series — a sum where each term is a fixed multiple of the one before. Geometric sums are the tool that answers "if things keep doubling, does the total blow up?" — and the answer is: no, the total is dominated by the final term.

PICTURE. Stack bars $1, 2, 4$ on top of each other on the left. On the right stands the single bar $8$ . The left stack ( $= 7$ ) is shorter than the right bar ( $= 8$ ). The whole history of copies is smaller than one more doubling.

$all past copies 1 + 2 + 4 + \dots + 2^{m} = one short of the next power 2^{m + 1} - 1 < double the last bar 2^{m + 1} \leq since 2^{m} \leq n 2 n$

$2^{m + 1} - 1$ = the exact total (a power of two minus one — think 0111...1 in binary). Notice it is one less than $2^{m + 1}$ : this off-by-one is what makes the copy cost strictly below $2 n$ .
$2^{m + 1} = 2 \cdot 2^{m}$ = double the largest single copy.
$2 n$ = because the largest copy $2^{m}$ can be at most $n$ , so double it is at most $2 n$ ; combined with the " $- 1$ ", the copy cost is $\leq 2 n - 1 < 2 n$ .

Step 6 — Add the two piles and divide

WHAT. Total work = cheap writes + expensive copies $= n + (2^{m + 1} - 1)$ , which is strictly less than $n + 2 n = 3 n$ . Amortized cost is total divided by the number of operations $n$ .

WHY. The word amortized means exactly this division: spread the whole bill across every push. Divide the total by $n$ and the $n$ 's cancel, leaving a plain constant. Because the copies are $2^{m + 1} - 1 \leq 2 n - 1$ (not exactly $2 n$ ), the true total is $< 3 n$ , so the average is strictly below 3 — and $\leq 3$ certainly holds.

PICTURE. Two stacked bars — a tall blue " $n$ writes" and a shorter orange " $< 2 n$ copies" — merge into one bar of height just under $3 n$ . Slice it into $n$ equal slivers; each sliver is height at most $3$ .

$Amortized cost = \frac{n writes + ( 2 ^{m + 1} - 1 ) copies \leq 2 n - 1}{number of pushes n} < \frac{3 n}{n} = 3 = O (1)$

numerator $n + (2^{m + 1} - 1)$ = the entire bill for the whole run — strictly under $3 n$ .
$n$ in the denominator = the number of things we're splitting the bill among.
$3$ = a constant upper bound — it does not grow with $n$ . That is what $O (1)$ means (see Big-O Notation).

Step 7 — Edge case: what about +1 growth? (why it fails)

WHAT. Repeat the count for +1 growth. Now a resize happens at every size $1, 2, 3, \dots, n - 1$ , and each copies that many items. The copy bars are $1, 2, 3, 4, \dots$ — an arithmetic series, not geometric.

WHY. We must show the other case so you never assume "bigger array = fine." With +1, each bar is only one taller than the last, not double — so the earlier bars are not dwarfed by the final one. They pile into a triangle.

PICTURE. A right triangle of bars $1, 2, 3, \dots, n - 1$ . Its area is the copy cost: base $n$ , height $n$ , area $\approx n^{2} /2$ . Compare against Step 5's thin geometric strip.

$copy cost_{+ 1} = 1 + 2 + 3 + \dots + (n - 1) = \frac{n ( n - 1 )}{2} = O (n^{2})$

the triangle's area $\frac{n ( n - 1 )}{2}$ = adding one-taller bars fills half of an $n \times n$ square.
dividing by $n$ gives amortized $\frac{n - 1}{2} = O (n)$ — grows with $n$ , so not constant.

Step 8 — Degenerate cases: empty and single push

WHAT. Two boundary inputs.

$n = 0$ : no pushes at all → total cost 0. Amortized is undefined ( $0/0$ ) but there is simply nothing to bound.
$n = 1$ : one push into an empty capacity-1 array → 1 write, 0 copies (nothing to copy yet) → total 1, amortized $1$ .

WHY. A guarantee that only works for large $n$ isn't a guarantee. We check the smallest inputs so no reader hits an unshown scenario. Happily, the bound " $\leq 3$ " holds from the very first push, where cost is $1 \leq 3$ .

PICTURE. Left panel: an empty array, cost counter at 0. Right panel: one blue box, cost counter at 1 — no orange copy bar exists yet.

Recall Check the tiny cases yourself

For $n = 1$ , amortized cost is? ::: $1/1 = 1 \leq 3$ ✅ — one write, zero copies. For $n = 0$ , is the array ever resized? ::: No — no pushes means no fills, no copies, total cost 0.

The one-picture summary

Everything above in a single frame: the blue writes grow like a straight line ( $n$ ), the orange doubling copies grow like a lower straight line ( $< 2 n$ ), their sum is a straight line ( $< 3 n$ ) — while the red +1 copies curve up as a parabola ( $n^{2} /2$ ). Straight lines divided by $n$ give a constant; the parabola divided by $n$ keeps climbing.

Recall Feynman: the whole walkthrough in plain words

You fill boxes with toys. Every toy you add costs 1 (you set it in a box). Sometimes a box is full and you must buy a bigger box and carry every toy over — that's the slow part. If you always buy a box twice as big, then the sizes you carry are $1, 2, 4, 8, \dots$ , and here's the wonderful thing: all the earlier carries added up are still smaller than the very last carry. So the whole lifetime of carrying is less than $2 n$ — as if each toy was carried barely twice. Add the $n$ set-downs and the (just under) $2 n$ carries, spread across $n$ toys, and every toy costs a bit under 3 on average. If instead you only bought one extra box each time, you'd carry toys again and again — $1 + 2 + 3 + \dots$ toys — which piles into a triangle of size $n^{2} /2$ , and now each toy costs a growing amount. The single idea: doubling keeps the copies a thin constant; adding lets them grow into a wall.

Connections

Amortized O(1) operations — the parent result this page derives visually.
Dynamic Arrays — the doubling array is exactly this structure.
Geometric Series — the Step 5 "sum stays under twice the last term" tool.
Big-O Notation — why a constant $3$ is $O (1)$ and $n^{2} /2$ is not.
Potential Method — an alternate route to the same $3$ (see parent).
Hash Tables · Load Factor — rehashing reuses this identical count.
Stack with Multipop — another amortized classic using the same style of argument.