How to fool the plot inspection heuristic?

Over here, Dave Clarke proposed that in order to compare asymptotic growth you should plot the functions at hand. As a theoretically inclined computer scientist, I call(ed) this vodoo as a plot is never proof. On second thought, I have to agree that this is a very useful approach that is even sometimes underused; a plot is an efficient way to get first ideas, and sometimes that is all you need.

When teaching TCS, there is always the student who asks: “What do I need formal proof for if I can just do X which always works?” It is up to his teacher(s) to point out and illustrate the fallacy. There is a brilliant set of examples of apparent patterns that eventually fail over at math.SE, but those are fairly mathematical scenarios.

So, how do you fool the plot inspection heuristic? There are some cases where differences are hard to tell appart, e.g.

example
example
example
[source]

Make a guess, and then check the source for the real functions. But those are not as spectacular as I would hope for, in particular because the real relations are easy to spot from the functions alone, even for a beginner.

Are there examples of (relative) asymptotic growth where the truth is not obvious from the function definiton and plot inspection for reasonably large n gives you a completely wrong idea? Mathematical functions and real data sets (e.g. runtime of a specific algorithm) are both welcome; please refrain from piecewise defined functions, though.

Answer

Speaking from experience, when trying to figure out the growth rate for some observed function (say, Markov chain mixing time or algorithm running time), it is very difficult to tell factors of (\log n)^a from n^b. For example, O(\sqrt{n} \log n) looks a lot like O(n^{0.6}):

plot
[source]

For example, in “Some unexpected expected behavior results for bin packing” by Bentley et al., the growth rate of empty space for the Best Fit and First Fit bin packing algorithms when packing items uniform on [0,1] was estimated empirically as n^{0.6} and n^{0.7}, respectively. The correct expressions are n^{1/2}\log^{3/4}n and n^{2/3}.

Attribution
Source : Link , Question Author : Raphael , Answer Author : dfeuer

Leave a Comment