This is not a post to argue for or against the big-O notation. Instead I just want to share an observation using a toy example.
Consider a dictionary data structure that supports access in logarithmic time. Suppose we have two implementations A and B where A is two times faster than B. (To make it precise but toyish, imagine an access takes $\log n$ time and $2 \log n$ time respectively where $n$ is the number of elements.)
How would this factor of two become important?
Well, when there is a hard upperbound on the amount of time allowed in an access, then the maximum number of elements that can be stored in A is actually the square of that of B.
It’s squared, not just doubled.
Now here’s something to think about. You can have a digital photo album that can store a maximum of two thousand photos or another one with four million photos. They are equally responsive on your computer. Which one would you prefer as a customer?
(Or, perhaps we can wait 18 months and be happy with the former one? :P)
14:56 on February 12th, 2006
Your point comes up in measuring the parameters of PCPs, in particular in the amount of random bits r used, since the length of the proof is bound by 2^{O(r)}.
E.g., a corollary of Irit Dinur’s proof of the PCP theorem is that there are PCPs for SAT that use log_2(n * poly log n) random bits and only O(1) queries suffice. There is no constant in front of the log_2, and the logarithm really is base-two. So, the resulting proof length is n*polylog n, as that’s the maximum length that it could possibly be.
14:58 on February 12th, 2006
Err, I meant that the proof length is bounded by 2^r… big-O notation is the enemy, eh?
22:10 on February 12th, 2006
Haha, gotcha!
In a way this post is arguing that the constant in front of polylog matters. So while I don’t exactly consider big-O to be the enemy all the time, for real-life applications, I can imagine we all have our doubts when choosing between, say, $2 \log^2 n$ and $20 \log n \log \log n$.