Makes the analysis completely worthless. The idea of the analysis is to evaluate asymptotic behaviour for large data sets. Of the idea ever a nonlinear cost of accessing the data, you should take it into account.

Suppose the memory is tree structured like typical TLB, you do get at least one extra log n factor. And actually there are even more costs on the way.