Comment by tillytal

Surely the main point is that

    O(n) + O(n) = O(2n) = O(n) = O(n + 1) = O(n) + O(1)

and the constant factors left out of O() often dominate execution time.

Cache performance is just one example of a constant factor, right?