Array — static, dynamic; cache locality; amortized O(1) append: Worked examples

This page is the stress-test for the parent Array note. There we derived the three big ideas (address formula, geometric growth, cache locality). Here we use them on every kind of input the topic can throw at you — small caps, big caps, a growth factor that isn't 2, an empty array, a resize that happens on the very first append, a real-world timing question, and an exam trap.

Read each [!example] statement, make a forecast before scrolling, then check your instinct against the steps.

The scenario matrix

First, the one symbol the whole page turns on, defined before the table uses it:

Now every problem about dynamic arrays lands in one of these cells. We will hit all of them.

#	Case class	What makes it special	Covered by
A	Cheap append (`size < capacity`)	just a write, no copy	Ex 1
B	Expensive append (`size == capacity`)	triggers a resize + copy	Ex 1, Ex 2
C	Doubling growth (growth factor $g = 2$ )	the classic amortized-O(1) case	Ex 2
D	Growth factor $g \neq = 2$ (e.g. $g = 1.5$ )	still O(1) amortized — must re-derive	Ex 3
E	Degenerate: empty array / first append	capacity 0 → what does "double 0" mean?	Ex 4
F	Additive growth (+k) — the trap	O(n²) total, O(n) amortized	Ex 5
G	Address arithmetic (static-array flavour)	pure `B + i·s`, sign/edge indices	Ex 6
H	Real-world timing (cache locality)	array vs linked list wall-clock	Ex 7
I	Exam twist (which grows slower: total copies)	compare two growth factors head-to-head	Ex 8

Example 1 — Cheap vs expensive appends (cells A, B)

Worked example Trace 4 appends, start cap 2,

$g = 2$ A vector starts with $cap = 2$ , $size = 0$ . You append 10, 20, 30, 40. For each append say: cheap (just write) or expensive (resize + copy how many)?

Forecast: guess how many of the four appends copy anything, and the total copies, before reading.

append 10 — size(0) < cap(2), so just write at index 0, size→1. Why this step? Rule 1 of append: room exists → O(1), no copy. Cheap.
append 20 — size(1) < cap(2), write at index 1, size→2. Cheap. Why this step? Same rule 1: size(1) is still below cap(2), so there is a free slot at index 1 — we drop the value in and bump size, no allocation, no copy. This is the ordinary O(1) case that happens for most appends.
append 30 — now size(2) == cap(2). Full! Allocate cap $2 \cdot 2 = 4$ , copy 2 old elements, then write. size→3. Expensive, copy 2. Why this step? Rule 2: no room → build bigger block, move everyone, then insert.
append 40 — size(3) < cap(4), write at index 3, size→4. Cheap. Why this step? Rule 1 again: the resize in step 3 doubled capacity to 4, so size(3) now sits below cap(4) and there is a spare slot at index 3. We just write and increment — no copy. This shows how one resize buys several subsequent cheap appends before the next full moment.

Verify: total elements copied $= 2$ . Only 1 of 4 appends was expensive. Final state: $size = 4$ , $cap = 4$ — the array is exactly full, the next append would resize. ✓

Figure — Array — static, dynamic; cache locality; amortized O(1) append

Figure description (Ex 1). A bar chart with one bar per append: append 10, append 20, append 30, append 40. Each bar has an orange base of height 1 = the single write every append does. The third bar (append 30) additionally carries a violet stack of height 2 = the two elements copied during its resize, so it stands three units tall while all others stay one unit tall and are labelled "cheap." A magenta arrow points at that tall bar reading "full: size==cap triggers resize." The single tall violet bar is the one expensive append; every other bar is a flat cheap write — that shape is the meaning of "amortized": rare spikes averaged across many flat writes.

Example 2 — Total copy cost with doubling (cell C)

Worked example

$n = 16$ appends, start cap 1, $g = 2$ : total copies? Append 16 elements into a fresh vector (cap 1, doubling). What is the total number of element-copies across all 16 appends, and what is the amortized cost per append?

Forecast: the parent note said total copies $< 2 n$ . With $n = 16$ that's $< 32$ . Guess the exact number.

Resizes fire when size == cap, i.e. at sizes $1, 2, 4, 8$ (the next resize would be at 16, but we stop at 16). Why this step? A resize can only happen at the exact moment the array is full, and "full" means size == cap. Since each resize doubles the capacity, the next full moment is twice as far away — so the trigger sizes themselves double: $1 \to 2 \to 4 \to 8$ .
At each resize we copy the current size before doubling: copy $1$ , then $2$ , then $4$ , then $8$ . Why this step? When you build the bigger block you must move every element that already exists into it, and the number that exists at that instant is exactly size (which equals the old cap). So the copy count at each resize equals the trigger size.
Total copies $= 1 + 2 + 4 + 8 = 15$ . Why this step? This is the Geometric Series $\sum_{j = 0}^{k} 2^{j} = 2^{k + 1} - 1$ with $k = 3$ : $2^{4} - 1 = 15$ . We use the closed form so we never have to add the terms by hand for large $n$ .

$T = 1 + 2 + 4 + 8 = 2^{4} - 1 = 15 < 2 n = 32 ✓$

Verify: amortized per append $= \frac{T + n}{n} = \frac{15 + 16}{16} \approx 1.94$ operations — a constant, independent of $n$ . That constant-ness is the whole point of Amortized Analysis and confirms O(1) amortized. ✓

Example 3 — Growth factor ≠ 2 (cell D)

Worked example

$g = 1.5$ (grow by half): is it still O(1) amortized? Some real libraries (e.g. many C++ std::vector implementations) use $g = 1.5$ , not $2$ . Suppose we append many elements starting from cap 1. Show the total copy cost is still $O (n)$ .

Forecast: doubling gave " $< 2 n$ ". Do you think ×1.5 is better (fewer copies) or worse (more copies)? Guess, then check.

First fix one symbol. Let $m$ be the number of resizes, i.e. the largest whole number such that $g^{m} \leq n$ (after $m$ resizes the capacity has reached about $g^{m}$ , and once that exceeds $n$ no further resize is needed). So $m \approx lo g_{g} n$ .

Capacities visited: $1, 1.5, 2.25, \dots$ i.e. roughly $c_{j} = g^{j}$ . The copies done at each resize are the sizes just before, roughly $g^{0}, g^{1}, g^{2}, \dots, g^{m}$ where $g^{m} \leq n$ (that upper index $m$ is exactly the resize count defined above). Why this step? Each resize copies "current size," and current size tracks the capacity, which grows by factor $g$ .
Total copies $\leq \sum_{j = 0}^{m} g^{j}$ — again a Geometric Series, but ratio $1.5$ instead of $2$ . Why this step? Adding up "how much we copied at each resize" is literally adding $g^{0} + g^{1} + \dots + g^{m}$ (one term per resize, and there are $m + 1$ of them); recognising it as a geometric series lets us replace an open-ended sum with a single closed-form fraction instead of tracing every resize.
Sum of a geometric series with ratio $g < 2$ but $g > 1$ : $\sum_{j = 0}^{m} g^{j} = \frac{g ^{m + 1} - 1}{g - 1} \leq \frac{g}{g - 1} n .$ Why this step? $g^{m} \leq n$ , and the closed form of the series is $\frac{g ^{m + 1} - 1}{g - 1}$ . Factor out to bound by a constant times $n$ .
Plug $g = 1.5$ : constant $= \frac{g}{g - 1} = \frac{1.5}{0.5} = 3$ . So total copies $\leq 3 n = O (n)$ . Why this step? $g = 1.5$ is the concrete factor the question gave us; substituting it into the constant $\frac{g}{g - 1}$ turns the general bound into a number we can compare against doubling's $2$ .

Verify — compare to doubling. For $g = 2$ the same formula gives $\frac{g}{g - 1} = \frac{2}{1} = 2$ , matching the parent's " $< 2 n$ ." For $g = 1.5$ the constant is 3 — more copying, so ×1.5 is slightly slower per element but wastes less memory (over-allocation is only 50% instead of 100%). Still $O (1)$ amortized because $\frac{g}{g - 1}$ is a finite constant for any $g > 1$ . ✓

Example 4 — The degenerate empty array (cell E)

Worked example Append into a vector with cap 0

A brand-new vector has $size = 0$ , $cap = 0$ . You call append(x). But $g \cdot 0 = 0$ — doubling zero gives zero! How does the append ever get room?

Forecast: what capacity does the array jump to on the very first append? Guess a number.

size(0) == cap(0) → the array is "full" (0 of 0 used), so a resize must fire. Why this step? The full-check is size == cap, and $0 == 0$ is true.
New capacity $= g \cdot cap = 2 \cdot 0 = 0$ — useless. So every real implementation special-cases this: if cap is 0, jump to a fixed small starting capacity (commonly 1 or 4). Why this step? Multiplicative growth can't escape zero; you need an additive seed exactly once.
With seed $= 1$ : cap $0 \to 1$ , copy 0 old elements (there are none), write x. size→1. Why this step? We pick the smallest useful seed, $1$ , because it makes every later doubling ( $1 \to 2 \to 4 \to \dots$ ) match the clean powers-of-two derivation the parent used, and it wastes the least memory for the many arrays that only ever hold a handful of items. (Libraries that expect larger arrays seed at 4 to skip the tiny first few resizes — a memory-vs-copies choice, not a correctness one.)

Verify: copies done $= 0$ (empty source). After the append: $size = 1$ , $cap = 1$ . This is exactly the "start cap 1" assumption the parent's derivation used — now you know where that 1 comes from. ✓

Edge check — appending into an empty array is still O(1) amortized: the one-time seed is a constant cost paid once, so it doesn't change the average.

Example 5 — The additive-growth trap (cell F)

Worked example Grow by

$+ 2$ each time, $n = 8$ appends A misguided vector grows capacity by a fixed +2 whenever full (start cap 2). Append 8 elements. Total copies? Amortized cost?

Forecast: the parent warned additive growth is $O (n^{2})$ . Do you think total copies here is closer to 8, or closer to 30? Guess.

Caps visited: $2, 4, 6, 8$ (each resize adds 2). Resizes fire at sizes $2, 4, 6$ (the append that fills each cap). Why this step? +2 growth means a resize almost every couple of appends — far more often than doubling.
Copies at each resize = current size = $2, 4, 6$ . Why this step? Just like the doubling case, a resize must move every element that already exists into the new block, and that count is exactly size at the moment of resize (which here equals the old cap $2, 4, 6$ ). The rule "copies = current size" is universal; only how often it fires changes with the growth policy.
Total copies $= 2 + 4 + 6 = 12$ . Why this step? This is an arithmetic series $\sum 2 j$ , not geometric — it grows like $n^{2}$ , not $n$ .

Verify — scale it up. For general additive growth by $k$ , resizes copy $k, 2 k, 3 k, \dots$ up to $\approx n$ , totalling $k (1 + 2 + \dots + \frac{n}{k}) = k \cdot \frac{( n / k ) ( n / k + 1 )}{2} \approx \frac{n ^{2}}{2 k} = O (n^{2})$ . Divide by $n$ : amortized $= O (n)$ — quadratic total, linear per append, the disaster the parent note flagged. With $n = 8, k = 2$ our formula predicts $\approx \frac{64}{4} = 16$ ; the exact small- $n$ count was $12$ (the approximation ignores rounding), same quadratic shape. ✓

Contrast: doubling 8 elements (start cap 2) copies only $2 + 4 = 6$ . Additive +2 copies $12$ — and the gap widens without bound as $n$ grows. That is why real dynamic arrays multiply.

Example 6 — Address arithmetic, edge indices (cell G)

Worked example

double d[100] (8 bytes each), base $B = 4000$ Give the address of d[0], d[99], and explain why d[100] is a bug even though the formula produces a number.

Forecast: guess addr(99) before computing.

Formula from the parent: $addr (i) = B + i \cdot s$ with $B = 4000$ , $s = 8$ . Why this step? Element $i + 1$ starts $s$ bytes after $i$ ; by induction, $i$ elements past base is $i \cdot s$ bytes.
$addr (0) = 4000 + 0 \cdot 8 = 4000$ — the base itself. Why this step? Index $0$ is the first element, so it sits at the very start of the block with zero offset: $0 \cdot s = 0$ . This is why arrays count from 0 — the index literally is "how many elements to skip," and you skip none to reach the first.
$addr (99) = 4000 + 99 \cdot 8 = 4000 + 792 = 4792$ . Why this step? To reach the 100th element (index 99) you skip the 99 elements before it, each $s = 8$ bytes wide, so the offset is $99 \cdot 8 = 792$ bytes added to the base.
$addr (100) = 4000 + 100 \cdot 8 = 4800$ — a valid-looking address, but it's one past the last element (valid indices are $0 \dots 99$ ). Reading it is undefined behaviour / out-of-bounds. Why this step? The math never "knows" the array's length; you enforce $0 \leq i \leq n - 1$ . This is the classic off-by-one.

Verify: the block spans $addr (0) = 4000$ up to $addr (99) + s - 1 = 4792 + 7 = 4799$ . So the last byte of the array is 4799; address 4800 is outside. ✓ Units check: bytes + (dimensionless index × bytes) = bytes. ✓

Example 7 — Real-world timing: array vs linked list (cell H)

Worked example Sum 1,000,000 ints — how many RAM trips?

You sum a contiguous array of 1,000,000 four-byte ints. Cache line $L = 64$ bytes. Estimate the slow-memory fetches, and compare to a Linked List holding the same numbers.

Forecast: guess the ratio of linked-list fetches to array fetches.

Elements per cache line $= L / s = 64/4 = 16$ . Why this step? One fetch loads a whole 64-byte line; that's $16$ neighbouring ints at once (see CPU Cache and Memory Hierarchy).
Array fetches $= \frac{n}{L / s} = \frac{1 , 000 , 000}{16} = 62, 500$ . Why this step? Because $addr (i + 1) - addr (i) = s$ is tiny and predictable, one fetch serves the next 15 reads for free — you only pay a slow RAM trip once per 16 elements.
Linked list: nodes are scattered, each next is a fresh line → up to $1, 000, 000$ fetches. Why this step? A linked-list node is malloc-ed independently, so consecutive nodes can sit anywhere in memory — the address gap between one node and the next is unpredictable and usually larger than a 64-byte line. So the neighbours that the cache line drags in are not the nodes you'll visit next; each next pointer jumps to an address the cache has never seen → a fresh miss per node.

Verify: ratio $= \frac{1 , 000 , 000}{62 , 500} = 16 \times$ fewer memory trips for the array — even though both are $O (n)$ in Big-O Notation. Big-O hides the constant; the cache line is that constant. This is why "same complexity" ≠ "same speed." In practice the array wins ~5–10× wall-clock (not the full 16×, because prefetching, TLB effects and partial locality soften the linked list's worst case). ✓

Example 8 — Exam twist: which factor copies less over $n$ appends? (cell I)

Worked example

$g = 2$ vs $g = 4$ : which does fewer total copies as $n \to \infty$ ? A quiz asks: "Doubling ( $g = 2$ ) vs quadrupling ( $g = 4$ ) — which has the smaller amortized copy constant?" No tracing allowed; use the closed form.

Forecast: more aggressive growth (×4) resizes less often. So does it copy less? Guess yes/no.

From Ex 3, amortized copy constant $= \frac{g}{g - 1}$ . Why this step? Total copies $\leq \frac{g}{g - 1} n$ , so per-append copies $\approx \frac{g}{g - 1}$ .
$g = 2$ : $\frac{2}{2 - 1} = 2$ . $g = 4$ : $\frac{4}{4 - 1} = \frac{4}{3} \approx 1.33$ . Why this step? We just substitute each concrete growth factor into the general constant $\frac{g}{g - 1}$ : for $g = 2$ the denominator is $1$ , giving $2$ ; for $g = 4$ the denominator is $3$ , giving $\frac{4}{3}$ . Comparing the two numbers is what the exam actually asks.
So $g = 4$ copies fewer elements per append ( $1.33$ vs $2$ ). Why this step? Bigger jumps mean resizes are rarer, so less total moving — the intuition holds.

Verify — the catch. $\frac{g}{g - 1}$ is decreasing in $g$ , so higher $g$ = fewer copies. But memory over-allocation is up to $(g - 1) \times$ = $300%$ waste for $g = 4$ vs $100%$ for $g = 2$ . So $g = 4$ trades memory for speed. The exam-correct answer: $g = 4$ does fewer copies ( $\frac{4}{3} < 2$ ), at the cost of memory. Both are still $O (1)$ amortized because $\frac{g}{g - 1}$ is finite for every $g > 1$ . ✓

Recall Which cells did we cover?

A,B (Ex1) ::: cheap + expensive appends C (Ex2) ::: doubling total copies = 15 for n=16 D (Ex3) ::: g=1.5 still O(1), constant 3 E (Ex4) ::: empty array seeds cap 0→1 F (Ex5) ::: additive +2 gives O(n²) total (12 copies for n=8) G (Ex6) ::: addr(99)=4792, addr(100) is out-of-bounds H (Ex7) ::: array 62,500 fetches vs list ~1,000,000 (16× fewer) I (Ex8) ::: g=4 constant 4/3 < g=2 constant 2

Connections

This page leans on Amortized Analysis and Geometric Series for the copy-cost sums, CPU Cache and Memory Hierarchy for Ex 7, and contrasts arrays with Linked List. The append pattern underlies Stack (Data Structure) (push = append) and the buckets of a Hash Table. Timing claims are stated in Big-O Notation, which is the language for saying "both are $O (n)$ yet one is 16× faster in practice."