Re:Faster Than Dijkstra?
by thbb123 on Saturday February 14, 2026 @03:29AM
(#47012757)
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.
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.