intermediate · layout
Same O(n), Very Different Wall Clock
Why can iterating an array be several times faster than iterating a linked list, when both are O(n)?
Practical scenario
A colleague benchmarks summing 10 million integers in a vector versus a linked list and finds the vector roughly 8× faster. They ask whether the benchmark is broken, since both are linear.
What it tests
- • Whether the candidate knows complexity describes operation counts, not time
- • Understanding of cache lines as the unit of transfer
- • Whether they can name the mechanism rather than just asserting "cache locality"