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

WHAT we do: apply $\text{addr}(i)=B+i\cdot s$ with $B=2000$, $s=4$, $i=7$. WHY this tool: the address of any element is computed, not searched — that is the whole point of contiguity. $\text{addr}(7)=2000+7\cdot 4=2000+28=2028$ Notice we never touched elements 0–6. Answer: 2028.

WHAT/WHY: size = elements you put in; capacity = slots allocated; a resize fires only when size == capacity.

• (a) size = 6 → 6 elements stored.
• (b) capacity = 8 → 8 slots allocated.
• (c) After one append size becomes 7, still $<8$. So no resize — it's a cheap O(1) write into slot index 6.

Answer: the array. The property is contiguity (contiguous memory with fixed element size). WHY: the CPU loads a whole cache line at once; array neighbours ride in together, so most reads are cache hits. A Linked List scatters nodes, so each next is likely a cache miss. Same Big-O, very different constant.

$\text{addr}(0)=4096+0\cdot 8=4096$ $\text{addr}(3)=4096+3\cdot 8=4096+24=4120$ $\text{addr}(10)=4096+10\cdot 8=4096+80=4176$ Gap: $\text{addr}(i+1)-\text{addr}(i)=s=8$ bytes — constant and predictable, which is exactly what lets the hardware prefetcher guess ahead. Answers: 4096, 4120, 4176; gap = 8.

WHY this tool: one memory fetch loads $L/s$ contiguous elements; scanning $n$ (recall: $n$ = how many elements we touch) costs $\approx n\cdot s/L=n/(L/s)$ fetches.

• (a) $L/s=64/2=32$ elements per fetch.
• (b) $800000/32=25000$ fetches (versus 800,000 if scattered).

Resizes fire when size == capacity, at sizes $1,2,4$ (each copies the current elements before doubling):

• append 1 → cap 1, write. copies 0
• append 2 → size(1)==cap(1): copy 1, cap→2
• append 3 → size(2)==cap(2): copy 2, cap→4
• append 4 → cap 4, write. copies 0
• append 5 → size(4)==cap(4): copy 4, cap→8 $T=1+2+4=7$ Bound check: $2n=2\cdot 5=10$, and $7<10$. ✓ Total copies = 7.

WHAT: sum the copies at every resize. Resizes occur at sizes $1,2,4,\dots ,2^k$ where $2^k\le n$. WHY these numbers: a resize copies the current count, then doubles capacity, so the counts copied are exactly the powers of two. $T=1+2+4+\cdots +2^k={\sum }_{j=0}^k{2}^j$ Deriving the geometric-series identity from scratch (do not just cite it — earn it). Call the sum $S$: $S=1+2+4+\cdots +2^k$ Now multiply every term by the ratio $2$: $2S=2+4+8+\cdots +2^{k+1}$ WHY multiply by 2? Because doubling shifts the whole list up by one term, so almost everything cancels when we subtract. Line up and subtract $S$ from $2S$: $2S-S=2^{k+1}-1⟹S=2^{k+1}-1$ Every middle term ($2,4,\dots ,2^k$) appears in both sums and cancels; only the new top $2^{k+1}$ and the old bottom $1$ survive. So: $T=2^{k+1}-1<2\cdot 2^k\le 2n$ Now the cheap writes. In our cost model each unit of work = "one element touched." Every one of the $n$ appends performs exactly one write of the new element into its slot (old[size] = x) — that is 1 unit each, so $n$ appends contribute $n$ write-units. These are separate from copy-units. Total work $=(\text{copies})+(\text{writes})\le 2n+n=3n=O(n)$. Divide by $n$ appends → $O(1)$ amortized. ∎ (This is the amortized argument.) The figure below plots exactly this — watch the cyan copy-total stay pinned under the amber $2n$ line.

How to read this figure. The horizontal axis is $n$, the number of appends so far; the vertical axis is the running total of elements copied. The cyan staircase jumps upward only at the rare resize points ($n=2,3,5,9,\dots$) and stays flat in between — visual proof that most appends copy nothing. The dashed amber line is the ceiling $2n$. The cyan staircase never crosses it: that gap is the $O(1)$-amortized guarantee made visible.

WHY additive fails: with a fixed step $c=10$, resizes happen at sizes $10,20,30,\dots$ — that is every 10 appends, and the count copied keeps growing linearly. There are about $n/10$ resizes, and the $m$-th resize copies $10m$ elements. The copies form an arithmetic series (not geometric — the terms grow by a constant difference $10$, not a constant ratio): $T\approx 10+20+30+\cdots +n={\sum }_{m=1}^{n/10}10m=10{\sum }_{m=1}^{n/10}m$ Deriving the arithmetic-sum ${\sum }_{m=1}^{p}m$ from scratch (call $p=n/10$). Write the sum forwards and backwards and add termwise: $\begin{array}{rl}\text{forwards: }& 1+2+\cdots +(p-1)+p\\ \text{backwards: }& p+(p-1)+\cdots +2+1\end{array}$ Each of the $p$ paired columns sums to $p+1$, so twice the sum is $p(p+1)$: ${\sum }_{m=1}^{p}m=\frac{p(p+1)}{2}$ WHY the pairing trick? Pairing the largest with the smallest makes every column identical, turning a sum into one multiplication — the classic Gauss argument. Substitute $p=n/10$: $T=10\cdot \frac{(n/10)(n/10+1)}{2}=\frac{(n/10)(n/10+1)\cdot 10}{2}\approx \frac{(n/10{)}^2\cdot 10}{2}=\frac{n^2}{20}$ (the $+1$ is negligible for large $n$). That is $O(n^2)$ total → dividing by $n$ appends gives amortized $O(n)$ per append. Terrible. The lesson: you must grow by a multiplicative factor (×2, ×1.5). The gaps between resizes must grow, not stay constant.

Elements per line: $L/s=64/4=16$.

• Array A (stride 1): consecutive elements share lines. Fetches $\approx 1000000/16=62500$.
• Array B (stride 16): each accessed element $i,i+16,i+32,\dots$ lands in a different line (they're exactly one line apart), so you touch a fresh line every read. Accesses made $=1000000/16=62500$, and each costs its own fetch → $\approx 62500$ fetches for only $62500$ elements used. The point: A gets 16 elements per fetch (locality wins); B gets ~1 useful element per fetch (locality destroyed by the stride). Same Big-O, but B wastes every cache line — a classic "cache-unfriendly access pattern."

(a) Yes. Any growth factor $g>1$ gives a geometric series with ratio $g$. Total copies: $T=1+g+g^2+\cdots +g^k=\frac{g^{k+1}-1}{g-1}<\frac{g}{g-1}\cdot n$ (This closed form is the same "multiply-by-$g$ and subtract" derivation as Solution 3.1, now with ratio $g$ instead of $2$: $gS-S=g^{k+1}-1$, so $S=\frac{g^{k+1}-1}{g-1}$.) With $g=1.5$: constant $\frac{g}{g-1}=\frac{1.5}{0.5}=3$, so $T<3n=O(n)$ → $O(1)$ amortized. (For $g=2$ the constant is $2$.) (b) Trade-off: ×1.5 wastes less memory (worst-case ~50% over-allocation vs ~100% for ×2) but copies more often (bigger constant, 3 vs 2). ×1.5 = memory-friendly; ×2 = fewer copies. Both are $O(1)$ amortized — you're choosing the constant.

append(x):
    if size == capacity:                 # array is full
        newcap = max(1, 2 * capacity)    # geometric growth
        B_new  = allocate(newcap * s)    # cost model below
        copy old[0..size-1] -> B_new     # O(n)  <-- the expensive part
        free(old);  B = B_new;  capacity = newcap
    old[size] = x                        # O(1) write
    size = size + 1

• Cheap branch (size < capacity): just the write + increment → O(1).
• Expensive branch (size == capacity): copy all size elements → O(n).
• The allocate cost model. We treat allocate(newcap * s) as O(1). WHY is that fair? A modern allocator reserves a block by handing back a pointer and recording the size in its bookkeeping — it does not touch every byte of the block (the memory is left uninitialised until you write it). So the reservation itself is a constant-time bookkeeping step; the genuine per-element work happens in the copy line, which we already charge as $O(n)$. (If instead you demanded zero-initialised memory, the zeroing would be $O(\text{newcap})$ — but that is still absorbed into the same geometric total, so the amortized result is unchanged.)
• Worst-case single append: $O(n)$ (the resize copy).
• Amortized append: $O(1)$ (Problem 3.1: total copies $<2n$ over $n$ appends). Why they differ: the $O(n)$ resize is rare — its cost, spread across the many cheap appends that follow, averages to a constant. Worst-case looks at one call; amortized looks at the whole sequence.

• (a) $n$ pushes with doubling: total $\le 3n=O(n)$ (copies $<2n$ plus $n$ writes).
• (b) pop just decrements size (no shrink assumed): each is $O(1)$, total $O(n)$.
• (c) Total work over $2n$ operations $=O(n)+O(n)=O(n)$, so per operation $=O(n)/2n=\mathbf{O}(1)$ amortized. That's why an array-backed stack is the standard, fast choice.

Resizes copy $1,g,g^2,\dots ,g^k$ with $g^k\le n<g^{k+1}$. Total copies use the geometric closed form derived in Solution 3.1 (multiply-by-$g$, subtract): $T={\sum }_{j=0}^k{g}^j=\frac{g^{k+1}-1}{g-1}<\frac{g^{k+1}}{g-1}\le \frac{g\cdot n}{g-1}$ using $g^k\le n\Rightarrow g^{k+1}\le gn$. So amortized copies per append: $\frac{T}{n}<\frac{g}{g-1}=C(g)$ This is a finite constant for every $g>1$ → $O(1)$ amortized. ∎ Behaviour of $C(g)=\frac{g}{g-1}$: it decreases as $g$ grows: $C(1.5)=3$, $C(2)=2$, $C(4)=\frac{4}{3}\approx 1.33$, and $C(g)\to 1$ as $g\to \infty$. Interpretation: bigger $g$ → fewer copies per element (approaching 1, the theoretical floor) but worse wasted memory (worst-case over-allocation $\to (g-1)\times$). So $g$ trades time-constant against space-constant. Real libraries pick $g\in [1.5,2]$ as the sweet spot.

No — a plain dynamic array cannot have $O(1)$ worst-case append. Proof by the pigeonhole of contiguity: to keep elements contiguous (which is required for $O(1)$ index access via $\text{addr}(i)=B+i\cdot s$), a full array must move to a larger contiguous block, and some append must pay the copy. If that copy stayed $O(1)$, you could only ever copy a constant number of elements, contradicting that the block holds $n$ of them. Hence at least one append is $\Omega (n)$ → worst-case is not $O(1)$. How to approach it: use incremental / geometric resizing with copy-spreading — during the "next" resize, copy a fixed few old elements per append (keep both blocks alive, migrate lazily). This bounds each append's work by a constant while preserving contiguous access on the new block. (This is the classic "amortized→worst-case deamortization" trick; contrast with a Hash Table or Linked List, which give different worst-case profiles.)

• (a) Block bytes $=16\times 4=64$. Lines $=64/64=1$ line.
• (b) New block bytes $=32\times 4=128$. Lines $=128/64=2$ lines.
• (c) Reading 16 contiguous ints sequentially: $16/(L/s)=16/16=1$ line-fetch to stream all of them. Contiguity makes even the copy step itself cache-efficient — the resize is $O(n)$ in element-work but touches memory minimally.

$\text{addr}(i)=B+i\cdot s$ ::: address of element i (base + index × element size) Elements loaded per cache fetch ::: $L/s$ (line bytes ÷ element bytes) Total copies, doubling, n appends ::: $\sum 2^j=2^{k+1}-1<2n=O(n)$ Amortized copy-constant for factor g ::: $C(g)=\frac{g}{g-1}$ (2 for ×2, 3 for ×1.5, →1 as g→∞) Additive (+c) growth total copies ::: arithmetic series $\approx n^2/(2c)=O(n^2)$ Worst-case single append (dynamic array) ::: $O(n)$ (the resize copy)