Danger of hidden constants
Godfrey Hardy, one of the greatest British mathematicians of the last century, wrote hundreds of research papers, and the wonderful “An Introduction to the Theory of Numbers” with E. M. Wright. Many of us learned the O-notation first from their book. In any event the O-notation appears in almost all theory papers. Many attribute the notation–incorrectly–to Edmund Landau: he popularized it but did not invent it. In any event we use O-notation all the time. It’s O-this and O-that.
Use and Misuse of Big O-Notation
The problem with O-notation is simple. Suppose that we prove that some algorithm runs in time . Is this better or worse than another algorithm that runs in time ? It depends. In the long run, clearly, algorithm will be faster. The economist John Maynard Keynes once said: “In the long run, we’re all dead.” So the fact that is eventually better may or may not matter.
The key, of course, is the hidden constant in the O-notation. If algorithm runs in time and algorithm runs in time , then for all practical cases I would rather run . This is the problem. What if we prove that there is an algorithm for SAT that runs in time . This may or may not have any practical significance. If the hidden constant is large, then it will be of no practical import. Of course, it would be a great mathematical result. You would have resolved the issue of P=NP. You would win awards, prizes, and be famous. But, the practical value would be nil.
The flip side of this is also true. If you prove that any algorithm for SAT requires time, then again the hidden constant matters. If the hidden constant is tiny, then this result will not show that SAT is really hard. Again you will win awards, prizes, and be famous, but the practical value would be nil.
The point is that these are not idle concerns, they have already happen. Many theory bounds have constants that make the asymptotic results not relevant. For example, the famous Robertson-Seymour theorem yields a algorithm for the recognition of certain graph properties. However, the hidden constant in this algorithm is huge, really huge, really really huge. Thus, while the result is a major achievement, it does not lead to a practical algorithm.
The problem happens often in lower bounds for approximation algorithms. Often these proofs are based on complex methods. I believe that when the proofs are completely unwound, the hidden constants will be immense. What does it mean to prove that there is no better than a approximation method if the hidden constant is extremely tiny? While this results, like the Robertson-Seymour work are beautiful, they could be misleading. If has to be for the bound to hold, then what are we really saying about the difficulty of approximating the problem?
The main open question that theory will have to address one day is to replace O-notation by some more exact model. We will at some point have to be able to really compare algorithms in a way that actually reflects they true performance.
One concrete challenge is to “unwind” some of the know algorithms and lower bounds, and discover their actual constants. For example, how realistic are the current lower bounds that are based on PCP’s? I wonder if they are realistic at all–could they require that the size of the problem be enormous? This in no ways takes away from their beauty, but it does take away from the practical impact. If the constants are huge, then we have an interesting paradox: we would have lower bounds for huge values of ; however, for realistic values of there could be fast algorithms. Strange, but possible.