3.2.1 · D5Linear Data Structures
Question bank — Array — static, dynamic; cache locality; amortized O(1) append
Recall
Reveal cards are one line each: read the left of :::, think, then check the right.
Symbols used on this page
Before any card fires, pin down the two letters that keep appearing. Look at the memory strip below: it is one long row of byte-cells, and an array lives inside it.
True or false — justify
Accessing a[i] gets slower as the array grows longer.
False — is one multiply plus one add regardless of ; the length never enters the formula, so access stays O(1).
A dynamic array's size and capacity are always equal.
False —
capacity ≥ size always, and after a doubling resize capacity can be nearly twice size; they coincide only momentarily right before an overflow.Amortized O(1) append means every single append is O(1).
False — the resize-triggering append is genuinely O(n); "amortized" is the average over many appends, not a promise about any one of them (see Amortized Analysis).
Growing a dynamic array by ×1.5 instead of ×2 breaks the amortized O(1) guarantee.
False — any constant multiplicative factor gives a Geometric Series total copy cost of O(n); ×1.5 just wastes less memory and resizes slightly more often, still O(1) amortized.
Growing by a fixed +100 slots each overflow gives amortized O(1) append.
False — additive growth resizes every 100 appends, and total copies still sum to ; dividing by leaves O(n) amortized. Only multiplicative growth works.
Arrays and Linked Lists have the same Big-O for scanning all elements, so they perform the same.
False — both are O(n), but arrays touch RAM ~ times fewer thanks to contiguous cache lines; in practice arrays run several times faster despite identical Big-O.
A static array can grow if you just keep writing past its last index.
False — its size is fixed at allocation; writing past the end corrupts whatever memory sits after the block (undefined behaviour), it does not extend the array.
An empty dynamic array with capacity == 0 can grow by "doubling" its capacity.
False — doubling stays forever, so the first growth must be special-cased ( or some base) before the doubling rule can ever take effect.
Doubling capacity means the array wastes O(n²) memory.
False — the waste is unused slots, at most
capacity − size ≤ size ≈ n, so O(n) space overhead — a constant factor over the data, never quadratic (see the Space overhead figure).Cache locality is a Big-O property of arrays.
False — Big-O ignores constant factors and the memory hierarchy; cache locality is a real-hardware constant-factor speedup invisible to asymptotic analysis.
Inserting at the front of a dynamic array is O(1) amortized like append.
False — front insertion must shift all elements one slot right every time; that is O(n) per operation with no amortization escape.
The doubling series — why it sums to O(n)
The "geometric growth ⇒ O(n)" claim deserves its own picture, not just a citation. Below, each bar is the copy cost of one resize; the tallest bar is the last resize before .
Spot the error
"Append is O(n) worst-case, therefore a loop of n appends is O(n²)."
The premise is right but the conclusion double-counts: the O(n) resizes are rare and shrinking-in-frequency; total work across n appends is O(n), so the loop is O(n), not O(n²).
"To find a[5] the CPU walks past elements 0–4."
No — the whole point of contiguity is that is computed directly; elements 0–4 are never read. Walking is what Linked Lists must do.
"Doubling copies 2·capacity elements, so the resize costs O(2n) = O(n²)."
A resize copies only the
size current elements once; O(2n) is just O(n), and the factor 2 is a constant absorbed by Big-O — nothing squares."Since capacity ≥ size, a[capacity-1] is always a valid element."
The slots between
size and capacity are allocated but unused garbage; only indices 0..size-1 hold real data. Reading a[capacity-1] when size<capacity returns junk."A Stack (Data Structure) built on a dynamic array has O(n) push because of resizing."
Push maps to append, which is O(1) amortized; the occasional resize is averaged away, so stack push is amortized O(1), not O(n).
"Prefetching helps Linked Lists just as much as arrays."
The hardware prefetcher predicts regular strides ( bytes apart). Linked-list
next pointers land at scattered, unpredictable addresses, so prefetch guesses wrong and each hop is a likely cache miss.Why questions
Why must array elements all be the same size?
So uses a single fixed stride ; mixed sizes would force storing or searching for each element's offset, destroying O(1) access.
Why does geometric growth make total copy work O(n) while additive growth makes it O(n²)?
Geometric resize sizes form a Geometric Series that sums to less than ; additive resizes form an arithmetic series which is O(n²).
Why does the CPU load a whole ~64-byte cache line instead of the one byte you asked for?
Real programs exhibit spatial locality — the next bytes are usually needed soon — so fetching a line amortizes the slow RAM trip across many upcoming accesses.
Why is over-allocating memory the deliberate price of O(1) amortized append?
Spare capacity lets most appends skip resizing; you trade up to ~2× memory for the guarantee that copying happens only occasionally, keeping the average cheap.
Why can a Hash Table use a dynamic array underneath and still care about resize cost?
Its bucket array must grow (rehash) when it fills; the same amortized-O(1) doubling argument keeps average insertion cheap despite the O(n) rehash.
Edge cases
What does append cost when size == 0 and capacity == 0?
It special-cases the first allocation ( base capacity, since doubling gives ) plus one write; a single O(1) event because there are zero elements to copy.
Exactly one append in a doubling schedule is expensive at each power of two — which ones are cheap?
Every append where
size < capacity (the vast majority); only appends hitting size == capacity at sizes pay the O(n) copy.Is addr(0) still valid for an empty array (size 0)?
The address is well-defined, but no element lives there; you may compute the pointer but must not dereference it.
For a 1-element array, does cache locality give any benefit?
No meaningful benefit — a single element fits trivially; locality pays off only when scanning many contiguous elements so neighbours ride in on the same line.
What happens to amortized O(1) append if you also shrink the array on every removal down to exact size?
You reintroduce frequent resizes; a remove-then-append oscillation at a power-of-two boundary can force a copy every operation, degrading to O(n). Shrink with hysteresis (e.g. only below 1/4 full) to preserve amortization.