In the RAM model, a single binary search takes O(log n) accesses. If nothing is specified, this is the model that's commonly used to analyse algorithms, and one

In the RAM model, a single binary search takes O(log n) accesses. If nothing is specified, this is the model that's commonly used to analyse algorithms, and one of its assumptions is that access to any memory location takes constant time. That this might not be true on actual machines is one of the shortcomings of that model, so you might say that it takes O(log² n) cycles on a certain machine. But the accesses also converge to the position where the element is, so the last couple of accesses will be in pages the TLB knows and that will even be in cache, so they'll take only a couple of cycles. Analysing this gets very complicated very quickly. In the end, the RAM model is just that: a model. No model will ever cover all the peculiarities of the hardware that things are actually implemented on, as that would be nearly impossible and in any case too complex to work with during analysis. You just have to be aware of its limitations and do lots of benchmarks if you want to maximize performance :)