Memory Representation

Here’s something strange: the CPU can hand you arr[4999999] out of a five-million-element array without looking at any of the other elements. No scanning, no searching — it jumps straight there. How can it possibly know where that element lives?

The answer is the single most important fact about arrays, and it explains both their superpower (instant access) and their weakness (expensive inserts). It’s all about how they sit in memory.

Visualizing Memory

Imagine memory as a long strip of slots. If each integer takes up 4 bytes, an array of 5 integers will occupy 20 consecutive bytes.

Hover over each cell below to see the address calculation in action:

The Address Formula

Because of this contiguous storage, the computer can calculate the address of any element instantly:

Address of Arr[i] = Base Address + (i * Size of Element)

For example, to find Arr[3]:

1000 + (3 * 4) = 1000 + 12 = 1012

This property allows O(1) random access, meaning accessing any element takes the same amount of time regardless of the array size. It doesn’t matter if the array has 5 elements or 5 million — accessing arr[0] is just as fast as accessing arr[4999999].

Recall the formula

Cover the line and write it yourself — given the base address, an index, and the element size, what’s the address?

def address_of(base, index, elem_size):
  # no loop, no search — pure arithmetic
  # ??? the O(1) address calculation
 
print(address_of(1000, 3, 4))   # -> 1012

Why Does This Matter?

The Speed Advantage

• O(1) Access: The CPU calculates the address with a single multiplication and addition. No searching required.
• Cache Friendly: Due to spatial locality, accessing one element often loads neighboring elements into the CPU cache. This means iterating through an array is extremely fast — the next element is likely already in the fast cache.
• Predictable Performance: No matter which element you access, the time is constant.

The Trade-offs

• Fixed Size: We need to know the size upfront (for static arrays). The downside is that resizing is expensive because we need to find a new, larger block of contiguous memory and copy everything over.
• Costly Insertions/Deletions: Inserting in the middle means shifting all subsequent elements to make room. Same for deletion.
• Memory Waste: If you allocate an array of size 1000 but only use 10 elements, you waste memory.

Stack vs Heap Allocation

Where your array lives in memory matters:

// Stack allocation -- fast, automatic cleanup
void stackExample() {
    int arr[100];  // Lives on the stack
}  // Automatically freed here
 
// Heap allocation -- flexible, manual cleanup
void heapExample() {
    int* arr = new int[100];  // Lives on the heap
    // ... use arr ...
    delete[] arr;  // Must free manually!
}

Different Data Types, Different Sizes

The element size in the address formula varies by data type:

Here’s how a double array looks in memory (8 bytes per element):

Quick Check

This is the why behind the costs you saw in basic operations — contiguity is exactly what makes indexing O(1) and middle-insertion O(n) (you have to physically shift bytes). Next: array algorithms, where this fast, predictable access is the foundation for two pointers, prefix sums, and sliding windows.