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.