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, and this chapter prices the other half. That other half is space: the extra memory a program burns while it works. Then we drop straight through the abstraction to the metal, where a genuinely unsettling fact is waiting. Two algorithms with the identical Big-O can run a hundred times apart in real seconds. The reason has nothing to do with the exponent on n. The whole way through, we keep asking the one question that actually 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, and you'll spend memory to buy speed on purpose. You'll even predict when a "slower-looking" layout will crush 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 start by pricing 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; it has to exist. We count only the scratch space the algorithm allocates on top of it. And here's the hook: two routines that hand back the byte-for-byte same answer can sit in completely different space classes.

Let's make that word "extra" concrete before we price anything. Say you hand a routine a playlist of 10,000 songs and ask for it reversed. The playlist itself is not part of the bill, because it existed before the routine ran. What we bill is everything the routine creates while it works: a loop counter here, a whole duplicate list there. Python lets us watch this directly with sys.getsizeof(), which reports the bytes an object occupies. So our method all chapter is simple and honest. We run the routine, measure what appeared, and ask how that number grows as n grows. If the scratch stays fixed while n climbs, the routine is frugal. If the scratch grows in step with n, we're paying rent on a second copy.

The cleanest split in space cost is in-place versus copying, and it's worth feeling the difference. An in-place routine rearranges the data it was handed, right where it sits. It allocates only a fixed handful of variables, a loop counter and a temp, no matter how big n gets. That's O(1) extra space, which we also call constant space. A copying routine builds a whole new structure the size of the input, so its bill is O(n) extra space. Now watch the exact 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 in from the ends toward the middle, swapping references as they meet. The list object's size stays byte-for-byte unchanged: we measured 80056 bytes before and after, zero extra. Line 7, [::-1], allocates a second list of the same length instead — 80056 more bytes, and that bill scales with n. Same output, different space class, and the built-in pair makes the same choice explicit. list.sort() sorts in place and returns None, so it costs O(1) extra. sorted() hands back a new list, which is O(n) extra: we measured a 100,000-element sorted() result at 800056 bytes, a full second copy.

And that number 80056 is not a mystery, so let's take it apart. A Python list doesn't hold your values directly — it holds references, one 8-byte pointer per element. Ten thousand elements times 8 bytes is 80,000 bytes of pointers. The remaining 56 bytes are the list object's own header, the fixed bookkeeping every list carries. Add them and you get 80,000 + 56 = 80056, exactly what we measured. Run the same arithmetic on the 100,000-element sorted() copy: 100,000 × 8 + 56 = 800056. When a measurement decomposes cleanly like this, you know you're seeing the real machine, and that's a habit worth keeping: predict the number, then measure it.

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, and the search becomes an instant jump. You spend O(n) space, and in return you buy back a factor of n in time. This one trade is the engine under two techniques you'll meet all volume: hashing (ch37) and memoization (ch40). It's worth seeing it raw, right now.

Let's feel the trade on four numbers before we name the problem. Say I read you 3, 9, 12, 7 and ask: do any two of them add to 16? The re-scanning way answers by checking every pair, and with four numbers that's six checks. The remembering way makes one pass and keeps a running memory. At 3 you'd need a 13 to finish, and you haven't seen one, so you remember the 3. At 9 you'd need 7, not seen yet either, and at 12 you'd need 4, same story. Then comes 7, you'd need 16 − 7 = 9, and 9 is sitting right there in your memory. Done in four steps, with no backward scanning at all. That little running memory is about to become a dict.

Take two-sum, a classic little question: is there a pair in a list that adds up to a target? The brute force tries every pair with two nested loops, which is ~n²/2 checks and O(1) extra space. The trade keeps a dict of the numbers you've already seen. For each new number, just ask "is target − x in there?" — and that's an O(1) question. One pass over the list gives you O(n) time, O(n) space. We ran both versions on n = 20,000 with a target that has no answer, so both must look at everything, which is 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, and that restart is where the n² comes from. The hashed version replaces that scan with the in seen test on line 11. The price is seen itself, a dict that grows to n entries. And the payoff was not subtle. On our machine (timings are hardware-dependent), the brute force took ≈8,793 ms while the hashed version took ≈2.0 ms. That's about a 4,300× speedup, bought with a dict of ~590 KB. You handed the machine half a megabyte and it handed back nearly four-thousandfold. Here is that trade drawn 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, and that picture is true. But it hid a secret the CPU spends enormous effort fighting: reaching those boxes is slow. A modern processor executes an instruction in a fraction of a nanosecond. A trip out to main memory (DRAM) costs it roughly 100 ns, and 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 is a cache: a small store of recently-used data kept close to the core. From fastest and tiniest to slowest and vastest, the ladder runs registers → L1 → L2 → L3 → RAM → SSD → disk.

It's fair to ask why we don't just build all memory as fast as L1 and skip the pyramid. Two hard physical walls say no, and the first is cost and density. Cache is built from SRAM, which spends about six transistors holding each single bit. Main memory is DRAM, which gets away with one transistor and a tiny capacitor per bit. SRAM is blazing but bulky and expensive, so you get megabytes of it, not gigabytes. The second wall is distance: signals cannot outrun the speed of light, and at 3 GHz one clock cycle lasts a third of a nanosecond. In that time, light itself covers only about 10 cm. Memory that answers within a cycle must sit physically next to the core, and next to the core is small real estate. The pyramid isn't a design fashion — it's physics sending an invoice.

The latencies of these levels span a range that's honestly hard to believe, so let's make it visceral. These are typical order-of-magnitude figures for a modern machine, not measured on yours, because real numbers vary by hardware. Nanoseconds mean nothing to human intuition, so we scale every level into human time instead. Every figure below is stretched by one rule — pretend an L1 hit takes 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. It guesses, using one simple bet.

That bet has a name: locality, and it comes in two flavours. Temporal locality is the bet that data you touched a moment ago, you'll touch again soon, so the cache holds on to recent arrivals. Spatial locality is the bet that after address 1000 you'll want 1001, so memory never hands over a lone byte. It delivers a whole 64-byte cache line, the neighbours riding along for free. Both bets are statements about your code, not about the hardware. A loop that sums a list front to back wins both bets on every single step. Code that hops to a random address each step loses both, every time. The hardware never changes its strategy — which means the difference between winning and losing lives entirely in how you arrange and walk your data. Hold that thought through the next section.

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 of the pyramid: Big-O counts operations, and it 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 can do the exact same number of accesses, same Big-O, and still run wildly apart. It happens when one touches memory in an order the caches love and the other in an order they hate. Big-O drops that hidden multiplier on the floor and calls it the constant factor, and the memory access pattern is what sets it.

Picture two ways to hold a million numbers, starting with a contiguous array that lays them end to end in one solid 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. Better still, the prefetcher sees your straight march and has the next line ready before you ask. Now take 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, which means a fresh cache miss per node. Seven-eighths of every fetched line is wasted, and the prefetcher is blind because there's no pattern to predict. Same n steps, same O(n), utterly different metal.

We didn't just assert this claim, because claims are cheap — we timed it. First we run the same math in two layouts, so the layout is the only thing that differs. One version sums ten million integers held in a Python list, a block of references pointing off to separately-boxed int objects. The other sums the same values 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)

The two runs did the same operation count, yet they landed ~8.6× apart (hardware-dependent). The array wins because it's a tight contiguous block that the caches and prefetcher love. The list scatters its int objects across the heap, which means pointer-chasing, a miss risk per element. And 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. Then we proved the effect is the access order and nothing else. We walked the identical data twice, once in sequential order and once through a random permutation, so the reads were the same and only the pattern differed. 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.

Those memory numbers deserve a quick unpacking, because "boxed" is doing all the work. In Python, the number 5 is not 8 bytes sitting in a slot. It's a full object on the heap, with a type pointer and a reference count wrapped around the actual digits, about 28 bytes for a small int. The list stores an 8-byte reference to that box, so each number really costs 8 + 28 = 36 bytes, split across two places in memory. Ten million of those is 360,000,000 bytes, and there's the ~360 MB. The NumPy array throws the boxes away and keeps just the raw 8-byte int64s, so ten million × 8 = 80 MB in one block. And the ratio checks out: 36 / 8 = 4.5, exactly the memory saving we measured. When the arithmetic and the measurement agree like that, you can trust you've understood the layout.

you type
# ---------- grid_walk.py, 1000 x 1000 = 1,000,000 ints ----------
$ python grid_walk.py

grid = [[r * 1000 + c for c in range(1000)] for r in range(1000)]

sum_rows_fast     # for row in grid: for x in row
sum_rows_indexed  # for r: for c: grid[r][c]      -- same order
sum_cols          # for c: for r: grid[r][c]      -- stride one row

# ---------- and the same question with the boxes removed ----------
big  = np.arange(16_000_000, dtype=np.int64)   # 128 MB
seq  = big[:2_000_000]     # 2,000,000 contiguous  -> 8 values per line
strd = big[::8]            # 2,000,000 strided     -> 1 value  per line
seq.sum(); strd.sum()      # identical addition count

you see
PURE PYTHON, 1000 x 1000
  sum_rows_fast       26.2 ms   x1.00
  sum_rows_indexed    43.5 ms   x1.66   <- subscripting alone
  sum_cols            53.4 ms   x2.04
  of the 2.04x column penalty, 1.66x is plain subscripting
  the access ORDER itself buys only    x1.23

NUMPY, same 1000 x 1000 int64 block
  m.sum(axis=1).sum()  0.198 ms   x132 faster than sum_rows_fast

UNBOXED, 2,000,000 additions each
  contiguous (8 values / 64-byte line)   0.370 ms
  stride 64B (1 value  / 64-byte line)   4.262 ms   x11.50

WHY PYTHON DILUTES IT
  sys.getsizeof(grid[0])     8856 bytes of POINTERS
  sys.getsizeof(grid[0][0])  28 bytes, and it lives elsewhere
  numpy row m[0].nbytes      8000 bytes, values in line

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 of Chapter 32 gave you the lens to choose the lower growth curve. This chapter installs the reflex that separates engineers who "know Big-O" from engineers 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. 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), and now you know its price. The 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 habit has a name worth loving — machine sympathy, writing code that flows the way the hardware wants to run.

One honest caveat before that reflex hardens. The memory you spend on a lookup table is not free-floating, because it competes for the same tiny caches as everything else you touch. A typical L1 holds a few tens of kilobytes, and an L3 tens of megabytes. Build a table far bigger than that and most lookups into it will miss to RAM, paying the very latency you were trying to dodge. Our two-sum dict still won hugely because, at ~590 KB, it sat comfortably inside the cache hierarchy, so its O(1) questions stayed genuinely cheap. So the trade is real, but it's priced in cache-sized coins. Spend space to save time, and then check where that space will actually live.

The everyday transfer here is real. "Buy time with space" is just writing it down. You don't re-derive a friend's phone number every time, because you stored it once for O(1) recall. "Respect locality" is keeping what you're using within reach, like the tools on the bench instead of 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?" That question is the difference between code that looks fast on paper and code that is fast on the metal.

# ---------- grid_walk.py ----------
import timeit, sys
import numpy as np

N = 1000
grid = [[r * N + c for c in range(N)] for r in range(N)]

def sum_rows_fast(g):
    total = 0
    for row in g:                 # one row = one contiguous block of references
        for x in row:             # neighbours, in stored order
            total += x
    return total

def sum_rows_indexed(g):
    total = 0
    for r in range(len(g)):
        for c in range(len(g[0])):
            total += g[r][c]      # SAME order, two subscripts per element
    return total

def sum_cols(g):
    total = 0
    for c in range(len(g[0])):
        for r in range(len(g)):
            total += g[r][c]      # every step jumps a whole row forward
    return total

assert sum_rows_fast(grid) == sum_rows_indexed(grid) == sum_cols(grid)
# all three agree: 499999500000

def ms(fn):
    return min(timeit.repeat(lambda: fn(grid), number=1, repeat=7)) * 1e3


# ---------- the three timings ----------
sum_rows_fast       26.2 ms   x1.00
sum_rows_indexed    43.5 ms   x1.66
sum_cols            53.4 ms   x2.04
  of the 2.04x column penalty, 1.66x is plain subscripting
  the access order itself buys only            x1.23

#   SPLITTING THE GAP
#     26.2 -> 43.5   is the SUBSCRIPT tax. Same order, same cache
#                    behaviour; the only change is g[r][c] instead of
#                    iterating the row object. Two BINARY_SUBSCR
#                    bytecodes per element, a million times over.
#     43.5 -> 53.4   is the ACCESS ORDER, and that is the cache bill:
#                    x1.23, not x100.


# ---------- why it is 1.23 and not 100 ----------
sys.getsizeof(grid[0])      -> 8856 bytes    # 1000 POINTERS + header + slack
sys.getsizeof(grid[0][0])   -> 28 bytes      # ONE boxed int, living elsewhere
m[0].nbytes                 -> 8000 bytes    # numpy: 1000 raw int64s, in line

#   A "row" is not a row of numbers. It is a row of 8-byte POINTERS, and
#   each pointer aims at a separate 28-byte PyObject on the heap. So even
#   the row-major walk misses the cache on nearly every element -- it just
#   misses on the pointer fetch a little less often. Column order makes
#   the POINTER fetch scattered too, and that is the whole x1.23.
#
#   The 100x in the latency table is the per-access truth. What you
#   measure end-to-end is that stall diluted by bytecode dispatch,
#   refcount traffic, and unboxing. Both numbers are honest; they just
#   measure different things.


# ---------- now remove the boxes, and the line does the talking ----------
big  = np.arange(16_000_000, dtype=np.int64)   # 128 MB, far past any cache
seq  = big[:2_000_000]     # 2,000,000 values, contiguous
strd = big[::8]            # 2,000,000 values, 64 bytes apart

  contiguous (8 values / 64-byte line)   0.370 ms
  stride 64B (1 value  / 64-byte line)   4.262 ms   x11.50

#   Identical addition count. seq touches 16 MB and gets 8 useful int64s
#   out of every 64-byte line it fetches -- one miss, then seven free
#   hits, with the prefetcher running ahead of the loop. strd touches all
#   128 MB and gets exactly ONE useful value per line, so it pays 8x the
#   memory traffic and the prefetcher's straight-line bet is worthless.
#   Eight times the lines, and the measured factor is 11.5 -- the extra
#   is the prefetcher, which helps the contiguous walk and not the other.
#
#   For comparison: numpy m.sum(axis=1) on the SAME million ints the
#   Python grid held came in at 0.198 ms, or 132x sum_rows_fast. Same
#   O(n), same additions. Layout and a compiled loop, nothing else.


# ---------- the takeaway you can act on ----------
#   1. In pure Python, prefer `for row in grid` -- it is the fastest
#      spelling and the clearest one, and it costs you nothing.
#   2. Do not expect a 100x from access order alone in a list of lists.
#      Measure the split before you claim a cache win; ours was 1.23.
#   3. When the walk is hot and the data is numeric, unbox it. That is
#      where the cache line stops being a footnote and becomes the bill.

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. →