If you instead iterate through an array of size K you will only pay O(√N + K) since it's only the first memory access that's random. Re-iterating over it will c

If you instead iterate through an array of size K you will only pay O(√N + K) since it's only the first memory access that's random. Re-iterating over it will cost O(K). This teaches us an even more important lesson: If you plan to iterate through it, use an array. This is rubbish. Re-iterating it is the same as iterating it the first time: if you array doesn't fit into cache, you're going to pay for pulling it from further out into the memory hierarchy. To anyone who doubts me: try it. Try iterating an array that fits entirely in L1 many times, then do the same with an array that has to be pushed out to swap. The slowdown will be considerably worse than linear.