33Space, and the memory hierarchy — why equal Big-O runs 100× apart

In Chapter 32 we sorted algorithms into a zoo of growth classes — O(1), O(log n), O(n), O(n²) — and learned to name any loop's curve in time. But time is only half the bill. Now we add the other half: space, the extra memory a program burns. Then we drop through the abstraction to the metal, where an unsettling fact is waiting. Two algorithms with the identical Big-O can run a hundred times apart in real seconds, and the reason has nothing to do with the exponent on n. All the way through, we keep asking the one question that matters — if the operation count is the same, what else is the machine charging me for? By the end you'll read the space cost of any routine at a glance, spend memory to buy speed on purpose, and predict when a "slower-looking" layout will beat a "faster" one — because you'll finally see the constant that Big-O throws away.

01Space is a bill too — count the extra memory

Let's price the other half of the bill. Space complexity is the same idea as time complexity, just pointed at memory instead of the clock: how much extra storage does an algorithm need as the input size n grows? Watch that word extra — it carries the whole idea. We don't count the input itself, since it has to exist. We count only the scratch space the algorithm allocates on top of it. Here's the hook: two routines that hand back the byte-for-byte same answer can sit in completely different space classes.

The cleanest split is in-place versus copying. An in-place routine rearranges the data it was handed. It allocates only a fixed handful of variables — a loop counter, a temp — no matter how big n gets. That's O(1) extra space (also called constant space). A copying routine builds a whole new structure the size of the input: O(n) extra space. Watch the same "reverse the playlist" idea land in both classes:

import sys
songs = list(range(10000))          # a 10,000-element list

songs.reverse()                     # IN PLACE: swaps ends inward, no new list
# sys.getsizeof before and after: 80056 -> 80056 bytes  (extra: 0)

rev = songs[::-1]                    # SLICE: builds a brand-new 10,000-element list
# sys.getsizeof(rev): 80056 bytes    -> a second full copy, O(n) extra

Line 4, .reverse(), walks two fingers from the ends toward the middle, swapping references. The list object's size is byte-for-byte unchanged — we measured 80056 before and after, so zero extra. Line 7, [::-1], allocates a second list of the same length — 80056 more bytes that scale with n. Same output, different space class. The built-in pair makes the choice explicit: list.sort() sorts in place and returns None (O(1) extra), while sorted() returns a new list (O(n) extra — we measured a 100,000-element sorted() result at 800056 bytes, a full second copy).

So an algorithm has two prices, time and space. The engineer's move is to realise you can pay one to lower the other →

02The trade that runs this whole volume: buy time with space

Here is the single most useful sentence in algorithm design: you can almost always trade memory for speed. If a routine keeps recomputing something, store the answer the first time and look it up forever after. If an inner loop keeps searching for a value, build a lookup table so the search becomes an instant jump. You spend O(n) space, and you buy back a factor of n in time. This trade is the engine under two techniques you'll meet all volume — hashing (ch37) and memoization (ch40) — and it's worth seeing raw, right now.

Take two-sum: is there a pair in a list that adds to a target? The brute force tries every pair — two nested loops, ~n²/2 checks, and O(1) extra space. Here's the trade: keep a dict of numbers you've already seen, and for each new number just ask "is target − x in there?" — an O(1) question. That's one pass, O(n) time, O(n) space. We ran both on n = 20,000 with a target that has no answer, so both must look at everything — the honest worst case:

def brute(nums, target):            # O(1) space, O(n^2) time
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return (i, j)
    return None

def hashed(nums, target):           # O(n) space, O(n) time
    seen = {}                       # <-- the memory we BUY
    for i, x in enumerate(nums):
        if target - x in seen:      # an O(1) question, not an O(n) scan
            return (seen[target - x], i)
        seen[x] = i
    return None

The brute version's inner loop (lines 3–5) restarts a full scan for every element — that's where the n² comes from. The hashed version replaces "scan for the complement" with the in seen test on line 11, and seen is the price: a dict that grows to n entries. The payoff was not subtle. On our machine (timings are hardware-dependent), the brute force took ≈8,793 ms and the hashed version took ≈2.0 ms — about a 4,300× speedup — in exchange for a dict of ~590 KB. You handed the machine half a megabyte and it handed back nearly four-thousandfold. Here is that trade as a curve, where every unit of memory you spend buys back a chunk of time:

Buying time with space assumes memory is one flat, uniform thing you simply "have." It isn't. Memory is a hierarchy, and that changes everything →

03Not all memory is one place — the hierarchy

Volume 1 drew RAM as one long row of numbered boxes. That's true, but it hid a secret the CPU spends enormous effort on: reaching those boxes is slow. A modern processor executes an instruction in a fraction of a nanosecond, but a trip out to main memory (DRAM) costs it roughly 100 ns. In that time, the core could have run hundreds of instructions. So chip designers stack a pyramid of progressively smaller, faster memories in front of RAM, each one a cache — a small store of recently-used data kept close to the core. From fastest and tiniest to slowest and vastest: registers → L1 → L2 → L3 → RAM → SSD → disk.

The latencies span a range that's hard to believe. These are typical order-of-magnitude figures for a modern machine (not measured on yours — real numbers vary by hardware), scaled into human time so you can feel them. Imagine an L1 hit took one second:

Read that pyramid again, because it reframes performance entirely. The CPU is a Formula-1 engine bolted to a supply chain. If the part it needs is in a register or L1, it's already in its hand. If it has to fall to RAM, it stalls for the human equivalent of a coffee break. Fall to disk, and it's waiting months. The whole game of fast code is keeping the data the CPU wants near the top of this pyramid — and the CPU can't do that alone. So it guesses, using one simple bet.

A 64-byte line, fetched on every miss, quietly holding eight of your neighbours. That single fact is why two O(n) loops can finish an order of magnitude apart →

04Two O(n) loops, one many times slower — the access pattern decides

Now the payoff. Big-O counts operations and treats every memory access as one unit of cost. The hardware does not. An access that hits cache is roughly 100× cheaper than one that misses to RAM. So two algorithms that do the exact same number of accesses — same Big-O — can run wildly apart. It comes down to whether one touches memory in an order the caches love and the other in an order they hate. The hidden multiplier Big-O drops on the floor, the constant factor, is set by the memory access pattern.

Picture two ways to hold a million numbers. A contiguous array lays them end to end in one block. Walk it front to back and every 64-byte cache line you pull delivers eight useful int64s in a row — one miss, then seven free hits — and the prefetcher, seeing your straight march, has the next line ready. Now a linked list: each number lives in its own little node, allocated whenever, scattered across the heap, each pointing to the next. Walk it and every node.next is a jump to an unrelated address. That means a fresh cache miss per node, seven-eighths of every fetched line wasted, and the prefetcher blind because there's no pattern to predict. Same n steps. Same O(n). Utterly different metal.

We didn't just assert this — we timed it. First, the same math in two layouts. We sum ten million integers as a Python list (a block of references pointing off to separately-boxed int objects), then as a NumPy array (the raw int64s packed contiguously). Same additions, same O(n):

import numpy as np
lst = list(range(10_000_000))          # 10M ints; Python list of references
arr = np.arange(10_000_000)            # 10M ints; contiguous int64 block

sum(lst)      # measured best: ~35.4 ms
arr.sum()     # measured best: ~ 4.1 ms   -> ~8.6x faster, same O(n)

Same operation count, yet ~8.6× apart (hardware-dependent). The array is a tight contiguous block the caches and prefetcher love, while the list scatters its int objects across the heap — pointer-chasing, a miss risk per element. The array is smaller too: we measured the list of ten million ints at ~360 MB (8-byte references plus a ~28-byte boxed int each) versus ~80 MB for the NumPy array — 4.5× less memory and faster. To prove the effect is the access order and nothing else, we then walked the identical data twice: once in sequential order, once through a random permutation, with the same reads and only the pattern different. Through NumPy's C loop over a 320 MB block, random order ran ~4.6× slower. A pointer-chase through Python's interpreter (which dilutes the effect with its own overhead) still ran ~2.3× slower. The exponent on n never changed. Only the cache did.

You've now seen the two hidden costs Big-O ignores: extra space, and the constant set by locality. The last move is to turn that into a habit →

05The 1% move: respect the constant, spend space on purpose

The growth zoo gave you the lens to choose the lower growth curve. This chapter installs the reflex that separates engineers who "know Big-O" from those who ship fast systems: Big-O is where you start, not where you stop. Once you've picked the right complexity class, two more questions decide real speed, and most people never ask them.

Question one: what will this cost in space, and can I trade it? When something is slow because it recomputes or re-scans, ask what you could store to make the repeat instant. That's the hashing/memoization move (ch37, ch40). Now you know its price is real memory, drawn from a finite budget, so you spend it deliberately, not reflexively. Question two: how will the data be laid out, and how will I walk it? Two designs with the same Big-O are not equal. The one that marches contiguously through memory, feeds the prefetcher, and keeps its hot data in cache will win. This is machine sympathy — writing code that flows the way the hardware wants to run.

The everyday transfer is real. "Buy time with space" is just writing it down: you don't re-derive a friend's phone number every time, you stored it once for O(1) recall. "Respect locality" is keeping what you're using within reach — the tools on the bench, not out in the garage. And the master habit is the one to carry into every problem for the rest of this volume. After you've found the right complexity, ask "what am I storing, and how am I walking it?" — because that question is the difference between code that looks fast on paper and code that is fast on the metal.

That paradox — an operation that's occasionally expensive yet genuinely cheap on average — is the whole of the next chapter: amortized analysis, the honest accounting that explains why a million appends stay flat despite the resize spikes. →