Why is accessing an array element O(1)?

Difficulty: 3/10

contiguous memory, pointer arithmetic, cache locality

Constant-Time Array Access

Array access is O(1) because an array stores elements at predictable, contiguous memory addresses. Given the base address, element size, and index, the runtime can calculate the target element's address directly without scanning previous elements.

javascript

1
Accessing A[0], A[100], or A[1,000,000] requires the same number of address calculations.
2
There is no dependency on the number of preceding elements.
3
Therefore, indexed read and update operations are O(1).
4
This assumes ordinary array access rather than operations that first require searching for an index.

Scenario Questions

0-2 years experience

2-5 years experience

1Your team notices a performance regression after switching from a vector to a linked list for storing session objects. Walk me through why array access is faster and what trade‑offs you’d consider.

Follow-up Questions