Arrays and Memory: How Indexing Works

An array is a contiguous block of memory holding a fixed number of elements of the same type. The key property that makes arrays powerful is this: if you know the memory address of the first element (called the base address), you can compute the address of any element in constant time.

The Indexing Formula

The memory address of the element at index i is:

address[i] = base_address + (i × element_size)

For an array of 32-bit integers (element_size = 4 bytes), stored starting at address 0x1000:

• array[0] → 0x1000 + 0 × 4 = 0x1000
• array[1] → 0x1000 + 1 × 4 = 0x1004
• array[2] → 0x1000 + 2 × 4 = 0x1008
• array[i] → 0x1000 + i × 4

The CPU performs this multiplication in a single clock cycle. That is why array indexing is O(1) — there is no searching, no traversal. The hardware computes the address directly.

Why This Matters for Performance

Because elements are contiguous, when the CPU needs array[0], it loads a cache line — typically 64 bytes — starting at that address. For 4-byte integers, that single memory access brings in 16 consecutive elements. When the next access requests array[1] or array[2], those elements are likely already in the fast L1 or L2 cache. This is called spatial locality.

See how this compares to linked lists.

Static vs. Dynamic Arrays

A static array has a fixed size determined at compile time. A dynamic array (like std::vector in C++, ArrayList in Java, or list in Python) grows when full. Growth typically doubles the capacity:

The resize copy is expensive, but it happens rarely (at capacity 1, 2, 4, 8...), so the cost is amortized across many O(1) inserts, making the average cost O(1).

Connection to Algorithm Choice

Understanding memory layout informs every algorithmic decision:

• Binary search relies on random access — you jump to the middle element. This is only O(1) on arrays (or array-backed structures), not on linked lists.
• Tracing an array insertion shows why inserting at the beginning or middle requires shifting every subsequent element.
• The linear search trace demonstrates how arrays benefit from cache-friendly sequential access.

Key Takeaways

1. Array indexing is O(1) because the CPU computes base + index × size in one cycle.
2. Contiguous storage means cache-friendly access — nearby elements are loaded together.
3. Insertion in the middle is O(n) because every element after the insertion point must shift.
4. Dynamic arrays amortize resize cost by doubling capacity.

Try It Yourself

Implement binary search on a sorted array to put the O(1) indexing property to work. See Practice: Implement Binary Search.

This article is part of the Algorithms Foundations learning path.