Spatial Locality vs Temporal Locality: Why the Same Big-O Runs 10x Slower

You write two loops. Both touch every element of a 1,000 x 1,000 matrix. Both are O(n²). One finishes in under a second. The other takes nearly fifteen. The code is almost identical. You stare at it for five minutes. Both loops look fine. They are fine. Your algorithm is fine. Your CPU, however, has opinions.

Those opinions are called spatial locality and temporal locality. Understanding them is the difference between explaining why your O(n) is faster than their O(n), and standing at a whiteboard making vague hand gestures about "memory stuff."

The Cache Hierarchy (or: Why Your CPU Is a Trauma Response)

Your CPU runs at 3-4 GHz. Main memory takes 60-100 nanoseconds to respond. To a CPU, that's 200+ idle cycles of staring at the ceiling waiting for RAM to finish its coffee. So every modern processor builds a cache hierarchy that keeps recently used data close to the cores:

Level	Size	Latency
L1 cache	32-64 KB	~1 ns / 4 cycles
L2 cache	256 KB to 1 MB	~4 ns / 12 cycles
L3 cache	6-32 MB	~15 ns / 40 cycles
DRAM	GBs	~60-100 ns / 200 cycles

A cache miss to DRAM costs roughly 50-100x more than an L1 hit. Big-O analysis implicitly assumes every memory access costs the same. This assumption is wrong in ways that matter in practice.

Locality of reference is the formal term for how predictably your program accesses memory. Two types. One is about location. The other is about time.

Spatial Locality: Your Neighbors Ride for Free

Spatial locality means that when you access one memory address, you will probably access nearby addresses soon after.

The CPU does not fetch just the byte you asked for. It loads an entire cache line, which is 64 bytes on virtually every modern processor (Intel, AMD, Apple Silicon). You're reading a 4-byte integer. The CPU loads that integer plus the fifteen neighboring integers beside it, all at once, into cache. Fifteen free rides. If your next access is one of those fifteen neighbors, it costs nothing. It's already there.

Sequential array traversal exploits this perfectly:

# Good spatial locality: sequential access
total = 0
for x in arr:
    total += x

Every loop iteration reads the next element in memory. The prefetcher sees the pattern, loads the next cache line before you even ask, and your loop proceeds at memory bandwidth speeds.

Linked list traversal is the opposite:

# Poor spatial locality: pointer chasing
node = head
while node:
    total += node.val
    node = node.next  # could be anywhere in RAM

Same O(n) complexity. Each step follows a pointer to an arbitrary memory address. The CPU loads a cache line, reads one integer, then immediately jumps somewhere else. The prefetcher gives up. You're waiting for DRAM on every node. Empirically, the array version is 5-10x faster for large inputs. Bjarne Stroustrup's 2012 talk showed roughly 82x faster for 500,000 sorted insertions comparing vector vs linked list. The Big-O doesn't see any of that.

Temporal Locality: Use It Before You Lose It

Temporal locality means that when you access a memory location, you'll probably access that same location again soon.

Cache lines get evicted when the cache fills up. Reuse data quickly and it stays warm. Come back too late and the line is gone, and you're paying the DRAM penalty again.

The simplest example is a loop counter. The variable i gets accessed every single iteration, so it lives in a register. Temporal locality at its most basic. More interesting: memoization. The entire point of caching subproblem results in dynamic programming is temporal locality:

for i in range(1, m+1):
    for j in range(1, n+1):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]

You computed dp[i-1][j] one row ago. If the table fits in L3 cache (6-32 MB), accessing it again costs almost nothing. Working set size matters here: if your DP table overflows cache, rows get evicted before you revisit them, and you're paying for DRAM on what looks like a simple lookup.

Two O(n²) Loops, 15x Apart

A 2D matrix in memory is a 1D array under the hood. Row-major order (C, Java, Python, Go, Rust, JavaScript) stores row 0 contiguously, then row 1, then row 2:

[0,0][0,1][0,2] | [1,0][1,1][1,2] | [2,0][2,1][2,2]
   row 0              row 1             row 2

Row-major traversal walks through memory sequentially. Column-major traversal jumps by n elements between each access. For a large matrix, that jump exceeds a cache line, so every access is a miss:

n = 1000
matrix = [[0] * n for _ in range(n)]

# Cache-friendly: sequential access, prefetcher loves this
def row_major(matrix):
    total = 0
    for i in range(n):
        for j in range(n):
            total += matrix[i][j]
    return total

# Cache-hostile: jumps 1,000 elements each step
def col_major(matrix):
    total = 0
    for j in range(n):
        for i in range(n):
            total += matrix[i][j]
    return total

Both loops are O(n²). On a 1,000 x 1,000 matrix, the row-major version is consistently 5-15x faster. The hardware prefetcher detects the sequential stride in row_major and pre-loads cache lines before your code reaches them. In col_major, the stride is 1,000 elements wide, the access pattern is incomprehensible to the prefetcher, and every element arrives cold from DRAM. This gap often exceeds what cache line arithmetic alone predicts, because the prefetcher is doing extra work in the good case that a back-of-napkin analysis misses.

Two loops. Same algorithm. Same Big-O. One is fifteen times faster. Neither compiler warns you.

When You Can't Have Both, Temporal Wins

Programs that get both types of locality are fast. Programs that get neither are the ones engineers file incident reports about. When you have to choose, temporal locality usually wins more because it eliminates the access entirely on a cache hit. Spatial locality reduces the cost per access. Eliminating is better than reducing.

LRU cache is the concrete example. It needs O(1) access and O(1) deletion, so it uses a hash map plus a doubly linked list. The linked list nodes scatter in memory, destroying spatial locality. The design accepts this on purpose: you compensate by keeping the working set small so hot entries stay in L1/L2 through temporal locality. The temporal hit rate carries the structure. Poor spatial locality is the price you pay.

Where This Shows Up in Interviews

Most interviewers won't ask you to benchmark matrix traversal. They also won't explicitly mention cache lines. But the locality insight changes which solution you propose, and how confidently you explain it.

Choosing arrays over linked structures. For most interview problems, an array-backed stack, queue, or deque outperforms a pointer-chained one at identical asymptotic complexity. Knowing why, and being able to say "linked list nodes scatter in memory so the prefetcher gives up," turns a design choice into a signal.

DP table iteration order. When you fill a 2D DP table in Python or Java, iterate row by row. Column-by-column over a row-major array wastes a cache miss on every step. Both orderings produce the correct answer. One is significantly faster. Choosing the right one and knowing why is the kind of depth that gets noticed.

String building vs concatenation. Concatenating strings in a loop in Python creates a new object on each iteration, and those objects scatter in memory. "".join(parts) allocates once and writes sequentially. Both are O(n) total characters. One exploits spatial locality and avoids repeated allocation. It's a one-word change with a real reason behind it.

Complexity analysis footnotes. If you reach for a BST or a heap with pointer indirection, a strong interviewer may ask whether your asymptotic bound reflects real performance. The honest answer involves cache behavior. Saying "this is O(log n) but each step is likely a cache miss, so in practice a sorted array beats it for small n" is a better answer than just "O(log n)."

Spatial and temporal locality come up in voice-based mock interviews as follow-up questions after you present a solution. Explaining why your O(n) beats another O(n) under realistic conditions is exactly the kind of depth that separates strong-hire answers from passing ones.