RAM — Random Access Machine

Core idea

The Random Access Machine (RAM) model is a simplified model used to analyze algorithms.

We assume basic operations take approximately constant time:

Read/write a value
Compare values
Basic arithmetic
Access an array element by index

Therefore, these are generally treated as O(1):

x = 10
a + b
a == b
arr[i]
arr[i] = 100

This is a theoretical model. Real hardware can have additional costs, but this model is appropriate for standard interview-level Big-O analysis.

Why array indexing is O(1)

Arrays use contiguous memory. The address can be calculated directly:

address = base_address + index × element_size

So arr[3] does not need to scan earlier elements.

Therefore:

arr[i] → O(1)

Access vs search

arr[3]

is O(1).

Searching for a value in an unsorted array may require checking every element:

Search → O(n) worst case

Best case can be O(1), but standard worst-case analysis is O(n).

Linked-list contrast

A linked list requires following links to reach an arbitrary index:

10 → 20 → 30 → 40 → 50

Therefore indexed traversal is:

O(n)

Loop analysis

An O(1) operation repeated n times is O(n):

for i in range(n):
    x = arr[i]

Nested loops give:

n × n = O(n²)

Key mental model

RAM model
    ↓
Basic operations ≈ O(1)

Array
    ↓
Contiguous memory
    ↓
Direct address calculation
    ↓
Index access = O(1)

Interview takeaway

“Arrays use contiguous memory, so the address of an element can be calculated directly from the base address, index, and element size. Therefore indexed access is O(1).”

Quick revision

Operation	Complexity
Basic arithmetic	O(1)
Array read `arr[i]`	O(1)
Array write `arr[i] = x`	O(1)
Unsorted array search	O(n)
Linked-list traversal to index i	O(n)