One block of memory
An array is a contiguous run of equally sized slots. That single fact explains every one of its costs: the address of element i is start + i × size, which is arithmetic, not searching — so reading a[500000] costs exactly what reading a[0] costs.
It also explains the expensive part. There is no room between slots, so putting something in the middle means moving everything after it along by one.
The costs
The trap in that table is shift. It looks like pop and costs n times more, so a queue built out of shift is quietly quadratic — an O(n) loop calling an O(n) operation.
| Operation | Cost | Why |
|---|---|---|
a[i] | O(1) | One multiplication and one addition |
a[i] = x | O(1) | The same |
a.push(x) | O(1) amortised | Usually free; occasionally the whole array is copied |
a.pop() | O(1) | Nothing moves |
a.unshift(x) / a.shift() | O(n) | Every other element slides |
a.splice(i, …) | O(n) | The same, from i onwards |
a.includes(x) / indexOf | O(n) | It has to look |
a.includes(x) when sorted | O(log n) | If you binary search instead |
Amortised: why push is free
When a growable array runs out of room it allocates a bigger block — typically twice as big — and copies everything across. That one push costs O(n). But the copies between doublings sum to less than n in total, so n pushes cost O(n) altogether: O(1) each, on average, for ever.
That is what "amortised" means: not "usually fast", but "the expensive cases are rare enough that the average is provably constant". Doubling is what makes the sum converge; growing by a fixed amount instead would make it quadratic.
capacity 1 → 2 → 4 → 8 → 16 → 32 …
copies 1 + 2 + 4 + 8 + 16 = 31 ≈ n for n = 32 pushesLocality is the part Big-O cannot see
A modern processor reads memory in cache lines of 64 bytes, and guesses what you will want next. Walking an array forwards is the single most predictable thing a program can do: every element you need is already in cache, fetched before you asked.
This is why an array of a million numbers is scanned several times faster than a linked list of the same million, even though both are O(n) — and why "the notation hides the constant factor" is not a small footnote.
Two-dimensional, and the order you walk it
Both loops are O(rows × cols). One of them is friendly to the cache and one fights it. When you meet a numerical routine that has been "optimised" and looks identical to the obvious version, this is usually what changed.
const grid = Array.from({ length: rows }, () => new Array(cols).fill(0));
/* row by row — each step is the next address in memory */
for (let r = 0; r < rows; r++) for (let c = 0; c < cols; c++) use(grid[r][c]);
/* column by column — every step jumps a whole row. Same O(n), several times slower */
for (let c = 0; c < cols; c++) for (let r = 0; r < rows; r++) use(grid[r][c]);