Even Knuth, in TAOP, acknowledges that using O(n) asymptotic behavior as a measure of performance is just a heuristic and not an absolute. Cache-awareness and

Even Knuth, in TAOP, acknowledges that using O(n) asymptotic behavior as a measure of performance is just a heuristic and not an absolute. Cache-awareness and structure discovery are 2 important tools of the engineer to optimize practical problems. If we wanted a reliable measure of the difficulty of a problem instance, it should rely on a function of O(K(n)) where K is the kolmogorov complexity of the input.