For the analysis in the article, it is enough to assume an unlimited amount of space into which you can put your memory as well as an unlimited amount of time. For your own analysis, you can of course make any assumptions you wish, but the author argues (and I agree with him there) that the spatial scaling O(sqrt(N)) for random access is both relevant in practice (as seen by the caching graph) and cannot be improved on when considering the laws of physics.
> The limits of the real world are good to remember but that does not invalidate Big O analysis.
No, it just means that you failed to take one specific bit into account and that your analysis may hence be less relevant to the real world. Much the same way we can say that integer addition is O(1), because usually we deal with fixed-size integers, we can say that memory access is O(1), because usually we deal with a fixed maximal memory size. Of course, integer addition is O(log(N)) and, according to the arguments made in the article, memory access is O(sqrt(N)).
The author assumes throughout the article uniformly random memory access. This is the worst case for a cache. If you're going to get down to the nuts and bolts of your implementation and come out of the high world of mathematics and Big O then you cannot just consider one element, namely, in this case caching. You should also consider your access pattern which very likely is not uniformly random and therefore probably does not fit the authors analysis. In fact, the only reason caching works is because the authors premise is generally wrong.
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.
> The limits of the real world are good to remember but that does not invalidate Big O analysis.
No, it just means that you failed to take one specific bit into account and that your analysis may hence be less relevant to the real world. Much the same way we can say that integer addition is O(1), because usually we deal with fixed-size integers, we can say that memory access is O(1), because usually we deal with a fixed maximal memory size. Of course, integer addition is O(log(N)) and, according to the arguments made in the article, memory access is O(sqrt(N)).