Amortized O(1) operations: Worked examples — Coding deep dive

Before we start, three words that will appear on every line — earned now, in plain English:

The scenario matrix

Every cell below is a distinct situation the doubling machine can be in. The examples that follow are tagged with the cell(s) they cover, so together they fill the whole grid.

Cell	Situation	Covered by
A	Smallest non-trivial run — trace every push, tiny $n$	Ex 1
B	Degenerate: empty array ( $n = 0$ ) and single push ( $n = 1$ )	Ex 2
C	Exact power of two ( $n = 8$ ) — resize on the very last push	Ex 3
D	Just past a power of two ( $n = 9$ ) — the worst-case latency spike	Ex 3
E	Different growth factor (grow $\times 1.5$ ) — is it still $O (1)$ ?	Ex 4
F	Failing factor: additive $+ k$ growth — quadratic blow-up	Ex 5
G	Hash-table rehash driven by load factor $α$	Ex 6
H	Shrinking / degenerate: pop-heavy sequence, avoid "thrashing"	Ex 7
I	Word problem — real-world sizing decision	Ex 8
J	Exam twist — mixed push/pop, potential-method proof	Ex 9

Prerequisites in play: Dynamic Arrays, Hash Tables, Load Factor, Geometric Series, Big-O Notation, Potential Method, Stack with Multipop.

Cell A — trace the smallest run

Worked example Example 1 — push 7 items, cap doubles from 1 (Cell A)

Start empty, capacity $1$ . Push items until size $= 7$ . Give the cost of each push and the total.

Forecast: guess the total cost before reading. (Hint: it should be under $3 \times 7 = 21$ .)

List the resize points. Capacities reached: $1, 2, 4, 8$ . A resize fires when we push into a full box — i.e. the push that would overflow the current capacity. Why this step? Because only a full box forces a copy; knowing where the box is full tells us where the expensive pushes are.
Cost each push.
- Push 1 → box(cap 1) was empty, write. cost 1
- Push 2 → box full(cap 1) → resize to 2, copy 1, write. cost 2
- Push 3 → box full(cap 2) → resize to 4, copy 2, write. cost 3
- Push 4 → room (cap 4, size becomes 4 = full), write. cost 1
- Push 5 → box full(cap 4) → resize to 8, copy 4, write. cost 5
- Push 6 → room (cap 8), write. cost 1
- Push 7 → room (cap 8), write. cost 1 Why this step? This is the definition of cost made concrete — copies happen only at capacities $1, 2, 4$ , i.e. on pushes $2, 3, 5$ . Note that push 4 merely fills cap 4 (no copy); it is push 5, the overflow, that triggers the copy of 4 elements.
Add them. $1 + 2 + 3 + 1 + 5 + 1 + 1 = 14$ . Why this step? Amortized cost = total ÷ n, so we need the honest total first.
Amortized. $14/7 = 2 \leq 3$ . ✅ Why this step? This is the definition of amortized cost applied directly — total cost of the sequence divided by the number of operations $n = 7$ . Getting $2$ (below the ceiling $3$ ) confirms that even in a tiny run, spreading the rare $5$ -cost push over the many cheap ones leaves each push constant on average.

Verify: split it. Writes = $7$ (one per push). Copies = $1 + 2 + 4 = 7$ (geometric series). $7 + 7 = 14$ . Matches. Copies $= 7 < 2 n = 14$ as promised. ✅

Read the figure below: the bars show each push's cost. Notice the three tall magenta bars (pushes $2, 3, 5$ ) are the resizes; all other bars are the flat cost- $1$ writes. The tallest bar (push $5$ , cost $5$ ) is where copying $4$ old elements happens. Your eye should see: most bars are short, few are tall — that visual is exactly what "amortized $O (1)$ " means.

Cell B — the degenerate ends

Worked example Example 2 —

$n = 0$ and $n = 1$ (Cell B) What is the total and amortized cost for pushing zero items? For one item?

Forecast: does "divide by $n$ " even make sense when $n = 0$ ?

$n = 0$ : no operations happen. Total cost $= 0$ . Why this step? Amortized cost is $\frac{total}{n}$ ; with $n = 0$ the ratio is $\frac{0}{0}$ — undefined. Amortized analysis only speaks about sequences of at least one operation. The honest statement is: the bound $\leq 3$ holds per operation, for every non-empty prefix.
$n = 1$ : one push into a freshly allocated cap- $1$ box. No copy. Total $= 1$ . Why this step? The very first push never resizes, so it is the cheapest possible case — a good sanity floor.
Amortized for $n = 1$ : $1/1 = 1 \leq 3$ . ✅

Verify: the bound $\leq 3$ is an upper bound; $n = 1$ gives $1$ , comfortably under. There is no lower-bound claim, so nothing is violated. ✅

Cells C & D — on and just past a power of two

Worked example Example 3 —

$n = 8$ vs $n = 9$ (Cells C, D) Compare pushing exactly $8$ items with pushing $9$ . Where is the worst single-push spike?

Forecast: which push is the most expensive of all — the 8th or the 9th?

$n = 8$ . Copies happen at sizes $1, 2, 4$ (when box was full at cap $1, 2, 4$ ). The push that overflows cap $4$ is push $5$ (resize to $8$ ). Pushes $6, 7, 8$ fit in the cap- $8$ box; push $8$ fills it but does not resize — it just writes into the last slot. Copies $= 1 + 2 + 4 = 7$ . Writes $= 8$ . Total $= 15$ . Amortized $= 15/8 = 1.875$ . ✅ Why this step? $n = 8$ lands exactly on capacity — the box ends perfectly full, no wasted slot, cheapest amortized case in this family.
$n = 9$ . The 9th push finds the cap- $8$ box full → resize to $16$ , copy 8, write. That single push costs $9$ — the biggest spike so far. Copies $= 1 + 2 + 4 + 8 = 15$ . Writes $= 9$ . Total $= 24$ . Amortized $= 24/9 \approx 2.667$ . ✅ Why this step? One item past a power of two forces a full copy of the entire array — this is the worst-case latency the parent warned about.
Contrast. $n = 8$ : no big copy. $n = 9$ : an $O (n)$ copy. Same rule, opposite feel. Why this step? Real-time systems care about the single $9$ -unit spike, not the $2.667$ average.

Verify: $n = 8$ : $7 + 8 = 15$ , $15/8 = 1.875 \leq 3$ . $n = 9$ : $15 + 9 = 24$ , $24/9 = 2.6 \overline{6} \leq 3$ . Both under the ceiling. ✅

Cell E — a different growth factor

Worked example Example 4 — grow by

$\times 1.5$ instead of $\times 2$ (Cell E) Does the constant $3$ change? Is it still $O (1)$ ?

Forecast: slower growth means more resizes. Does that break $O (1)$ ?

Why a Geometric Series still saves us. With factor $r = 1.5$ , the copy costs form $c, cr, c r^{2}, \dots$ up to $\approx n$ . Any geometric series with ratio $r > 1$ summed backward from its largest term $n$ is bounded by $n + \frac{n}{r} + \frac{n}{r ^{2}} + \dots = n \cdot \frac{1}{1 - \frac{1}{r}} = n \cdot \frac{r}{r - 1} .$ Why this tool? We use the infinite geometric sum $\sum_{i \geq 0} x^{i} = \frac{1}{1 - x}$ (with $x = \frac{1}{r} < 1$ ) as a clean upper bound on the finite sum — it answers "does adding infinitely many shrinking copies still total a finite multiple of $n$ ?" Yes.
Plug $r = 1.5$ : copy cost $< n \cdot \frac{1.5}{0.5} = 3 n$ . Why this step? Compare with doubling's $\frac{2}{2 - 1} = 2$ , giving $2 n$ . Slower growth → bigger constant.
Total and amortize: writes $n$ + copies $< 3 n$ → total $< 4 n$ → amortized $< 4 = O (1)$ . ✅ Why this step? Bigger constant ( $4$ vs $3$ ), same big-O. The factor sets the constant, not the growth class.

Verify: doubling constant from formula $= 1 + \frac{2}{2 - 1} = 3$ (matches parent). Factor $1.5$ constant $= 1 + \frac{1.5}{0.5} = 4$ . Both finite → $O (1)$ . ✅

Read the figure below: it plots total copy cost against $n$ for three growth rules. The two geometric curves ( $\times 2$ bounded by $2 n$ , $\times 1.5$ bounded by $3 n$ ) are straight lines — linear, hence $O (1)$ amortized. The additive $+ 1$ curve (Ex 5) bends sharply upward — a parabola, the quadratic blow-up. The whole lesson of Cells E and F is captured in that one contrast: straight lines stay cheap, the curve does not.

Cell F — the factor that fails

Worked example Example 5 — additive growth

$+ k$ (Cell F) Grow the box by a fixed $+ 10$ slots each resize. Total copy cost for $n$ pushes? Amortized?

Forecast: $+ 10$ feels generous. Trap or fine?

Count resizes. Capacities: $10, 20, 30, \dots$ — a resize every $10$ pushes, so $\approx n /10$ resizes. Why this step? Additive growth makes resizes frequent — proportional to $n$ , not $lo g n$ .
Copy cost per resize grows. Resize $j$ copies about $10 j$ items. Total copies $\approx 10 (1 + 2 + \dots + \frac{n}{10}) = 10 \cdot \frac{( n /10 ) ( n /10 + 1 )}{2}$ . Why this tool? This is an arithmetic series $1 + 2 + \dots + m = \frac{m ( m + 1 )}{2}$ , which grows like $m^{2}$ — the opposite of geometric.
Simplify. $\approx \frac{n ^{2}}{20} = O (n^{2})$ . Amortized $= O (n)$ — not constant. ❌ Why this step? Confirms the parent's rule: any additive $+ k$ gives $O (n)$ amortized regardless of how big $k$ is.

Verify: for $n = 100$ , $k = 10$ : resizes copy $10 + 20 + \dots + 90 = 450 \approx \frac{10 0 ^{2}}{20} = 500$ . Grows quadratically → amortized $\to \infty$ . ❌ (correctly fails). ✅

Cell G — hash-table rehash

Worked example Example 6 — insert with

Load Factor cap $α \leq 0.5$ (Cell G) An open-addressing hash table rehashes (doubles + re-places every key) whenever $α = \frac{size}{capacity}$ exceeds $0.5$ . Insert $n = 100$ keys starting from capacity $4$ . Total rehash work?

Forecast: rehash copies everything, like a resize. Same $O (1)$ ?

When does a rehash fire? At $α > 0.5$ , i.e. size $>$ capacity/2. From cap $4$ : rehash when size hits $3$ (→cap $8$ ), then $5$ (→ $16$ ), $9$ (→ $32$ ), $17$ (→ $64$ ), $33$ (→ $128$ ), $65$ (→ $256$ ). Why this step? Keeping $α \leq 0.5$ keeps probe chains short → $O (1)$ per probe; the trigger is the load factor, not "box full."
Rehash cost = geometric. Each rehash re-places the current size: $3 + 5 + 9 + 17 + 33 + 65 = 132$ . Why this step? Identical structure to array copies — a geometric-ish series bounded by $< 2 n$ .
Total & amortize. Writes $100$ + rehashes $132$ = $232$ . Amortized $= 232/100 = 2.32$ . ✅ Still $O (1)$ (assuming a good hash → $O (1)$ probes). Why this step? Rehashing = resizing + re-placing; the cost class is the same as Dynamic Arrays.

Verify: rehash sizes $3 + 5 + 9 + 17 + 33 + 65 = 132 < 2 n = 200$ . Total $232$ , amortized $2.32 \leq 3$ . ✅

Cell H — shrinking without thrashing

Worked example Example 7 — pop-heavy sequence & the halving rule (Cell H)

A stack both pushes and pops. If we halve capacity the instant size drops to capacity/2, alternating push/pop at the boundary would resize on every op — "thrashing." What rule avoids it, and what's the amortized cost?

Forecast: where should the shrink threshold sit — at $1/2$ or lower?

Diagnose the trap. Full box cap $4$ , size $4$ . Push → grow to $8$ (copy 4). Pop → size $4$ = cap/2 → shrink to $4$ (copy 4). Push again → grow… every op costs $O (n)$ . ❌ Why this step? A shrink threshold equal to the grow threshold leaves no slack — one op flips you across the line repeatedly.
The fix: shrink at $1/4$ full, halve to $1/2$ . Now after a resize the size is far from both boundaries; you must do $Θ (capacity)$ cheap ops before triggering another resize. Why this step? This gap is the "credit buffer" — it guarantees enough cheap operations between expensive ones to pay for them (the accounting method).
Amortized cost. With grow-at-full / shrink-at-quarter, both grow and shrink copies are spread over $Θ (n)$ cheap ops → amortized $O (1)$ per push and per pop. Why this step? Same geometric-series accounting, now applied to a two-sided sequence.

Verify: grow threshold $1.0$ , shrink threshold $0.25$ ; gap $= 0.75 > 0$ , so $\geq 0.75 \cdot cap$ cheap ops between resizes → amortized $O (1)$ . With gap $0$ (shrink at $0.5$ ): thrash. ✅

Cell I — real-world sizing

Worked example Example 8 — word problem: log ingest (Cell I)

A server appends log lines to a dynamic array. It expects $1, 000, 000$ lines. Memory is tight: measured right after a resize (the worst moment, when the new box is emptiest), you may waste at most $\sim 50%$ of the box on empty slots. Doubling leaves the box only half full right after a resize, so its just-resized waste is $\sim 50%$ — which is exactly at the limit and grows toward $\sim 100%$ extra slots relative to the data only in the transient before it fills. Choose a growth factor that keeps just-resized waste comfortably under $50%$ while staying $O (1)$ . Estimate the amortized cost.

Forecast: which factor trades a bit of speed for less wasted memory?

Define waste precisely. Right after a resize by factor $r$ , the box holds its old contents in a box $r$ times larger, so it is $\frac{1}{r}$ full → the just-resized waste fraction is $waste = 1 - \frac{1}{r}$ (fraction of the box that is empty). This is the single, consistent measure we use throughout. Why this step? The two earlier phrasings (" $50%$ waste" and " $100%$ extra slots") were confusing because they measured different things; we fix on one — empty fraction of the box just after resizing.
Match factor to budget. Doubling ( $r = 2$ ): waste $= 1 - \frac{1}{2} = 50%$ — at the limit. Choosing $r = 1.5$ : waste $= 1 - \frac{1}{1.5} = \frac{1}{3} \approx 33%$ — safely under $50%$ . Why this step? Waste is governed by the same factor knob as the time constant — pick $r$ once, get both.
Amortized cost at $r = 1.5$ . From Example 4, constant $= 1 + \frac{1.5}{0.5} = 4$ . So $\leq 4$ writes per line, $O (1)$ . Why this step? Confirms we stay constant-time while trimming memory.
Decision. Use $r = 1.5$ : worst-case (just-resized) waste $= \frac{1}{3} \approx 33%$ (under the $50%$ budget), amortized cost $\leq 4$ . Why this step? Meets both the memory constraint and the $O (1)$ speed requirement.

Verify: waste at $r = 1.5$ = $1 - 1/1.5 = 1/3 \leq 0.5$ ✅; time constant $= 1 + 1.5/ (1.5 - 1) = 4$ , finite → $O (1)$ . ✅

Cell J — exam twist (potential method, mixed push/pop)

Worked example Example 9 — prove a mixed push/pop sequence stays

$O (1)$ via Potential Method (Cell J) Let $m$ denote the old capacity just before a resize. Using the potential $Φ = 2 \cdot size - capacity$ , show: (a) a cheap push, (b) a resize push (a concrete resize with old capacity $m = 4$ , so $4 \to 8$ ), and (c) a plain pop each have amortized cost $O (1)$ — so any interleaving of pushes and pops is amortized $O (1)$ .

Forecast: the resize push has actual cost $5$ — how does $Φ$ hide the big copy, and does a pop ever go negative?

(a) Cheap push, size $4 \to 5$ , cap stays $8$ . Actual $= 1$ . $ΔΦ = 2 \cdot (5 - 4) = 2$ . Amortized $= actual + ΔΦ = 1 + 2 = 3$ . Why this step? Amortized cost in the Potential Method is defined as actual cost plus the change in potential; each cheap push deposits $2$ units into $Φ$ — building credit for the next copy.
(b) Resize push, old capacity $m = 4$ , size $4 \to 5$ , cap $4 \to 8$ . Actual $= copy m 4 + write 1 = 5$ . $Φ_{before} = 2 \cdot 4 - 4 = 4$ , $Φ_{after} = 2 \cdot 5 - 8 = 2$ , so $ΔΦ = 2 - 4 = - 2$ . Amortized $= actual + ΔΦ = 5 + (- 2) = 3$ . Why this tool? The stored-up $Φ$ pays for the spike: the $- 2$ drop absorbs part of the $5$ , leaving the smooth $3$ . This is precisely how the potential method cancels the $O (n)$ copy — the credit built up in part (a) gets spent here.
(c) Plain pop (no shrink), size $5 \to 4$ , cap stays $8$ . Actual $= 1$ (remove one element). $ΔΦ = 2 \cdot (4 - 5) = - 2$ . Amortized $= 1 + (- 2) = - 1 \leq 1$ . Why this step? A pop releases $2$ units of potential; its amortized cost is even below its actual cost, and $Φ = 2 \cdot 4 - 8 = 0 \geq 0$ stays valid — the bank never goes negative while the array is $\geq$ half full.
Resolve (a) and (b) together, then conclude. Both a cheap push and a resize push cost the same amortized $3$ — the resize's huge actual $5$ was smoothed down to $3$ by the potential drop that the cheap pushes had funded. Adding the pop ( $\leq 1$ ): every operation type is $O (1)$ amortized. Because amortized costs simply add over a sequence, any interleaving of pushes and pops totals $O (# ops)$ → amortized $O (1)$ per operation. Why this step? A uniform per-op bound is stronger than aggregate averaging; it holds even for an adversary who picks the worst push/pop order.

Verify: cheap push $1 + 2 = 3$ ✅; resize push $Φ_{before} = 4$ , $Φ_{after} = 2$ , $5 + (2 - 4) = 3$ ✅; pop $1 + (- 2) = - 1 \leq 1$ and $Φ_{after,pop} = 2 \cdot 4 - 8 = 0 \geq 0$ ✅.

Recap

Recall Which cells failed the

$O (1)$ test, and why? Only Cell F (additive $+ k$ growth) fails ::: arithmetic series → $O (n^{2})$ total → $O (n)$ amortized; every multiplicative-factor case (Cells A–E, G, I) and the two-sided stack (H, done right) stay $O (1)$ .

Recall What single number changes when you change the growth factor?

The amortized constant (e.g. $3$ for $\times 2$ , $4$ for $\times 1.5$ ) ::: the big-O class stays $O (1)$ ; only the constant $1 + \frac{r}{r - 1}$ moves.

Connections

Amortized O(1) operations — parent; this page is its full case-matrix.
Geometric Series — the bound $1 + \frac{r}{r - 1}$ used in Cells D, E, I.
Dynamic Arrays — Cells A–F.
Hash Tables · Load Factor — Cell G rehash.
Stack with Multipop — Cell H shrinking.
Potential Method — Cell J proof.
Big-O Notation — the class every cell is measured against.