Contiguous Memory: Why arr[i] Is Instant

"An array's magic isn't that it holds many things. It's that it holds them in a row, so it can find any one of them with arithmetic instead of searching."

A Row of Identical Boxes

Picture memory as an endless street of numbered houses. An array is a block of identical, equal-size boxes placed back-to-back on that street, starting at some address. The 0th box is at the start. The 1st box is right after it. The i-th box is exactly i box-widths past the start.

That layout is the whole trick. To find element i, the computer doesn't look through the array — it computes the address directly: address = base + i × box_size. One multiply, one add, jump straight there. That's why arr[5] and arr[5_000_000] take exactly the same time: both are a single address calculation. This is called random access, and it's the array's defining superpower.

Everything About Arrays Follows From This

Once you see "equal boxes in a row," every array property becomes obvious:

Indexing is O(1) — just address math.
The boxes must be equal size — otherwise the address formula breaks. That's why arrays hold one type, and why languages store variable-size things (like strings) as arrays of pointers to them.
Inserting in the middle is O(n) — there's no gap; you must shift every later box over to open one.
The size is fixed at the low level — growing means allocating a bigger block and copying (exactly the doubling you saw in amortized analysis).

An array is equal-size cells in a contiguous block. That single fact gives you O(1) random access (address = base + i × size) and explains every other cost the array has.

The Quiet Bonus: Cache Locality

There's a second gift hiding in "contiguous." When the CPU reads one array element, it pulls a whole neighboring chunk into its ultra-fast cache, betting you'll want the neighbors next — and with an array, you usually do. So scanning an array isn't just O(n) in theory; it's fast O(n) in practice, because the hardware is feeding you the next elements before you ask. Hold onto this — when we meet linked lists, their scattered memory throws this bonus away, and it matters more than the Big-O suggests.

Pippa's Confession

I knew arr[i] was O(1) long before I knew why. I thought the computer was just "fast at finding things." When Dad drew the street of boxes and the base + i × size formula, it stopped being magic — the computer isn't finding element i, it's calculating where it must be and going straight there. Understanding the why turned a memorized fact into something I could reason from.

Code

The address formula, made visible·python

from array import array

# A true contiguous array of 64-bit ints (Python's `array` is tightly packed).
arr = array('q', [10, 20, 30, 40, 50])   # 'q' = signed 8-byte integers

# Random access: any index, same cost. No scanning.
print(arr[0], arr[4])        # 10 50 — both via address math

# The address formula the computer uses, made explicit:
base = arr.buffer_info()[0]   # starting memory address of the block
size = arr.itemsize           # bytes per element (8 for 'q')
for i in range(len(arr)):
    addr = base + i * size    # base + i * box_size  <- O(1) for any i
    print(f"arr[{i}] = {arr[i]:>2}  lives at address {addr}")

# Notice the addresses go up by exactly `size` each step: the boxes are
# truly back-to-back. That contiguity is what makes arr[i] instant.

Exercise

An array of 4-byte integers starts at memory address 1000. Without code, compute the address of element 0, element 7, and element 250. Then explain in one sentence why inserting a new value at index 0 would force the computer to touch every existing element.

Hint

address = 1000 + index × 4. Element 7 is at 1028. For the insert: index 0 has no free gap, so every element must slide one box to the right to open it — that's the O(n).

A Row of Identical Boxes

Everything About Arrays Follows From This

The Quiet Bonus: Cache Locality

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0