Big Oh analysis is looking at the asymptotic behavior of an algorithm. In these analyses, the thing which gets done "more" will always overshadow the thing which gets done less. As an example, consider an algorithm which does $O(n)$ disk operations at a cost of 1,000,000,000 units each, and $O(n^3)$ comparisons at a cost of 1 unit each. Obviously for small numbers of n, the disk operations will be the dominating part of the cost. However, as we get to large n, like 1,000,000,000, we see that we do 1,000,000,000 disk operations, for a total cost of 1,000,000,000,000,000,000 and we do 1,000,000,000,000,000,000,000,000,000 comparisons, meaning we spent literally a billion times more on the comparisons than on the disk reads, even though they are very light weight on their own.
This is not always the story we want. For many practical algorithms, we are not operating on such awful huge datasets where those small comparisons start to add up. In these cases we may do other things. In the case of "offline algorithms," which operate on databases on disks, we may measure the number of reads. Or we may even recognize that its cheaper to load a "page" of values all at once, so we try to measure how many pages have to get loaded.
This sort of study is useful, but it is not well captured in a simple Big Oh analysis. It typically has to account for what the hardware is good at, making the analysis more specialized. For example, there are cryptographic algorithms which are designed to be very inefficient on a GPU architeture, but very efficient on a CPU architecture.
My personal favorite of these is a particular disjoint set algorithm that came up when I was working on some fun threading problems. The complexity of it was one of those exotic things with O(log log N) terms showing up. But in the conclusion of the paper, they had to admit that their algorithm had some aspects which had such an ungodly large time constant that the less advanced algorithms were better for basically any dataset which fit onto a modern disk farm. Once your dataset started to move into the extabyte size scale, their algorithm started to earn its salt!
binary_search
over a sorted linkedlist
is defined to have complexity $\mathcal{O}(\log_{2} N)$ (comparisons), whereas the actual complexity is going to be $\mathcal{O}(N)$ (number of pointer jumps).// This is just a case of model mismatch: In some theoretical (or early computer) models, the number of comparisons dominated. Nowadays, the comparison is quick, at least compared to memory lookup, so a different model fits better. $\endgroup$ – hoffmale Mar 23 '20 at 22:01