Static Arrays

## What the question is really testing An interviewer asking this is not checking whether you can compute a complexity class. Both loops visit every reading exactly once and both are O(n); if that were the whole story, they would take the same time. The question is whether your complexity claims come from a mental model of memory or from a memorised table. A candidate with the model can explain a 20x gap without ever changing the O; a candidate without it says "they're both O(n), so they perform the same" and stops. ## Memory does not move one value at a time Processors read memory in fixed-size blocks called **cache lines** — 64 bytes on most mainstream hardware today. Ask for a single 4-byte reading and the machine fetches the whole 64-byte line containing it and installs that line in cache. There is no such thing as fetching four bytes from main memory. That single fact drives everything else: - A contiguous array of 4-byte readings packs **16 readings per line**. The loop pays one memory trip and then gets fifteen further readings from cache, each costing a couple of cycles instead of a couple of hundred. - Values reached through scattered references live wherever the allocator happened to put them. Each one lands in a different line, so the loop pays roughly **one memory trip per reading** and throws away most of every line it fetched. The ratio of useful bytes to fetched bytes is the whole game. This is what **spatial locality** means: if you touch an address, you are very likely to touch its neighbours soon, so the hardware bets on that and prefetches the neighbourhood. ## Prefetching and overlapped misses There is a second, equally large effect. Modern chips contain a **hardware prefetcher** that watches the address stream and, when it detects a simple pattern — a forward walk, a fixed stride — issues loads for the next lines before the program asks for them. A sequential scan is the easiest pattern in the world to predict, so by the time the loop needs line *k+1*, it has already arrived. Scattered access defeats this in two ways. First, the addresses look random, so there is no stride to detect. Second, and worse, the *next* address is stored inside the data you just loaded, so it cannot even be computed until the current fetch completes. That serialises the misses: latency, then latency, then latency, each round trip fully exposed. A contiguous scan issues many independent misses at once and overlaps their latencies (memory-level parallelism); a reference chase can only ever have one outstanding. Roughly: sequential access is limited by memory **bandwidth**, scattered access by memory **latency**, and latency has improved far less over the decades than bandwidth has. ## Why the same array can be laid out either way The two shapes in the question are not exotic. Runtimes make genuinely different structural choices here: systems languages such as C and Rust store an array of records as one contiguous block of inline bytes, while managed runtimes such as the JVM and CPython commonly store an array of *references* to separately allocated values. The logical structure — "an array of readings" — is the same; the memory behaviour is not. That is why "is it an array?" is a weaker question than "are the values themselves contiguous?" ## Where the effect appears and where it does not - **Small inputs hide it.** If every reading fits in cache, both loops read from cache and the gap shrinks to a small factor. The ratio widens as the working set outgrows each cache level, then stabilises once both are served from main memory. - **Compute-bound loops hide it.** If each element costs an expensive computation, memory latency overlaps with useful work and the layout matters much less. The 20x figure belongs to a loop that does almost nothing but add. - **Write-heavy or randomly-updated workloads** change the picture again, because scattered writes also dirty many lines. ## How to say it in an interview State the invariant first — *the complexity is the same; the constant factor is not, and constant factors are not noise* — then name the two mechanisms (cache-line granularity plus prefetching, and overlapped versus serialised misses), then say how you would confirm it: time both shapes across several input sizes and watch where the curve bends. Asserting "contiguous is faster" is a slogan; explaining *how many lines each loop touches* is an answer.