How To Avoid O-Abuse and Bribes
An experimental approach to asymptotic analysis
Bob Sedgewick is an expert on the analysis of algorithms–one of the best in the world. This is not too surprising since he is a PhD student of Donald Knuth, who coined the term analysis of algorithms. Bob is also famous for his textbooks on algorithms and more recently his monograph on the analysis of algorithms with Philippe Flajolet. The last is a required book for anyone trying to understand the performance of an algorithm.
I have many stories about Bob. One of the strangest is the time that we were offered a bribe. For the record we did not take the bribe–although the statute of limitations is probably long run out on us. Also for the record the bribe offer was very smooth, so we could be wrong–no it was a bribe offer.
At the time Bob was the chair of the department of computer science at Princeton. For a variety of reasons there was a mathematician, we will call X, that was not going to be kept on at the Princeton mathematics department. This department is perhaps the best in the world, so that should not come as a shock.
The complication is that X was sort of a computer scientist. For reasons that I did not understand then, nor do I understand now, there were people in the political world that really wanted X to stay at Princeton. Powerful people. So far fine. It’s nice to have friends in high places. The trouble began when Bob was “asked” to a meeting with them. I was brought along for support, and it turned out that was a good idea.
The meeting was strange. They spoke highly of X. We agreed and said that we had a mechanism for hiring faculty. For starters, X should send us a resume, which would start the hiring review process. They nodded, but said why could we not just hire X. Bob repeated again and again that there was a process–and on it went.
Finally, one of the senior political types made it very clear that we personally would be very happy if we just hired X. No, he did not open a briefcase of cash, but his meaning was clear. Bob and I repeated the mantra, have X send in the resume. The meeting finally ended.
As soon as Bob and I were outside, we looked at each other and Bob said, “that was a bribe offer, no?” I agreed. A very strange affair all around. By the way X went elsewhere and did just fine.
How to Not to Abuse O-Notatation
Bob has a simple idea that I find quite compelling–I will present it in his own words. Think of this as a guest post. His initial “this” refers to an algorithm that we were discussing via email.
This example brings to mind the idea of rampant misuse of O-notation and an easy way to fix it that I’ve been teaching and using lately. Suppose that you think that the running time of algorithm is and another is . With O-notation, you have nothing to test with an experiment. But in almost all cases where you are going to run an experiment, it is reasonable to use notation to express a hypothesis. In this case, you would hypothesize that the running time of the first is and the second is for some constants and . So the ratio of the running times should be . Then if you run the same experiment for and take the ratio , all the constants cancel and this ratio of ratios approaches . Under the hypothesis, running the experiment for larger should give a better approximation to . Or, you can just run an experiment and solve for the constants to predict running time.
In short, experimental verification of hypotheses is easy with notation and impossible with O-notation. Despite that fact, O-notation is widely misused to predict and compare algorithm performance.
Bob then added, in his next email:
But actually log factors are not so important with this approach. For an unknown algorithm, we hypothesize , find by computing for as large an (and as many experiments) as we can afford, then use the actual running time to solve for . This gives very accurate predictions. Essentially the log factor is absorbed into the constant, which
is not so bad for large .
Try Bob’s idea out. Does this simple idea work on interesting problems?