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.
Today’s post is on the potential for abuse with the famous 
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 
In short, experimental verification of hypotheses is easy with
Bob then added, in his next email:
But actually log factors are not so important with this approach. For an unknown algorithm, we hypothesize 
is not so bad for large
Open Problems
Try Bob’s idea out. Does this simple idea work on interesting problems?
What is the title of Sedgewick and Flajolet’s monograph? My Google-ing skill seems to be off today.
Sedgewick and Flajolet’s book is “An Introduction to the Analysis of Algorithms”. You can find it here as well as a link to it at Sedgewick’s homepage.
My favourite book to learn programming what the one by knut.
I was thinking that O is often missused because in many algorithms you do not know when the iterations are going to end ,because they can depend stronly on the data they are processing, so you can not infer the order the algoerithm might have.
Maybe I am wrong, maybe you can just put always the higher possible one.
But I was thinking about the turing test about finishing time.
Can anybody explain in more detail?
Some colleagues of mine, Simon Goldsmith, Alex Aiken, and Dan Wilkerson, wrote a paper that tries to fit an implementation’s performance to a power-law, i.e. solving for a and b in T(N) ~= aN^b , using the implementations run time on different workloads. They are more fine grained than just looking at the final running time, in that they actually look at how often each basic block executes. This turns out to work surprisingly well and in some cases discovered performance bugs in implementations:
“Measuring empirical computational complexity”
http://portal.acm.org/citation.cfm?id=1287681
Their tool is available here:
http://trend-prof.tigris.org/
Nice stuff! That sounds similar to the automated performance testing/analysis system I put together recently: http://ndickson.wordpress.com/2009/07/09/inventor-performance-viewer/
Good to know that some other people are working on this front too. :)
I was taught that O(f) is the set of functions eventually bounded above by f times some constant, Ω(f) is the set of functions eventually bounded below by f times some constant, and θ(f) is the intersection of O(f) and Ω(f). So your squiggly-line symbol designates an equivalence class that is the same as θ(f).