4 of 32 · 5 min
Arrays, and why index 0 is instant
An array is a run of memory holding items of the same size, one after another. Everything an array is good and bad at follows from that one sentence.
Why indexing is O(1)
marks[0] marks[1] marks[2] marks[3]
| | | |
1000 1004 1008 1012 <- addresses, 4 bytes eachmarks[2] is not a search. It is arithmetic:
address = start + (index × size)
= 1000 + (2 × 4)
= 1008One multiplication and one addition, whether the index is 2 or 2,000,000. That is what O(1) means here.
What it costs
Everything is contiguous, so inserting in the middle means moving everything after it:
| Operation | Cost | Why |
|---|---|---|
| Read by index | O(1) | Arithmetic |
| Change by index | O(1) | Arithmetic |
| Insert at end | O(1)* | Usually free, see below |
| Insert at start | O(n) | Everything shifts right |
| Delete from middle | O(n) | Everything shifts left |
| Search unsorted | O(n) | Look at each |
| Search sorted | O(log n) | Binary search, page five |
The asterisk
Python's list and Java's ArrayList grow by allocating a bigger block and copying. That copy is O(n), which sounds like appending should be O(n).
It is not, because they double. Growing from 8 to 16 costs 8 copies and buys 8 free appends. Averaged over many appends the cost per append is constant, which is called amortised O(1).
Two dimensions
A 2D array is still one run of memory. grid[2][3] in a grid of width 5 is element 2 × 5 + 3 = 13. Which is why looping rows-then-columns is faster than columns-then-rows on a large grid: the first walks memory in order and the cache keeps up, the second jumps.