The author does address this point in part three of the series where he compares access times to a small area of a larger memory region. Even with absolutely sequential access to an array of size K, you first have to find this particular array in your larger memory region of size N, giving you total cost to iterate over the full array as O(sqrt(N) + K).

I am not sure how costly it is to iterate through your entire memory (assuming a no-op), but I would argue that eventually you reach some bottleneck and end up at O(sqrt(N)+N), too.