23
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Actually, I proposed it as a tip to understanding the problem. $\endgroup$ – Dave Clarke Mar 29 '12 at 8:05
  • $\begingroup$ @DaveClarke: I know; I used your initial formulation merely as a provocative opener. No offense intended. $\endgroup$ – Raphael Mar 29 '12 at 8:29
23
$\begingroup$

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}$.

$\endgroup$
15
$\begingroup$

Here is another (admittedly rather constructed) example, but still one I find remarkable. It is intended to show that plots can be very misleading for judging asymptotic growth.

The following plots show two functions $f$ and $g$ — disclosed below ;) — in different ranges. Remarkably, both functions are monotonically (strictly) increasing, (infinitely often) continuous differentiable and convex, so they are “nice” in many respects.

Can you guess which of the functions grows (asymptotically) faster?

plot of f and g up to 2000 plot of f and g up to 10,000 plot of f and g up to 200,000

The answer: $f\sim g$, i.e. the functions are asymptotically equivalent. The functions are $$f(x) = x^2$$ $$ g(x) = \iint \sin(\log(x))+1 \;dx\,dx = x^2\Bigl(1 - \tfrac{3}{5} \cos(\log(x)) + \tfrac{1}{5} \sin(\log(x)) \Bigr)\;. $$

So $g$ is essentially $x^2$, i.e. the same as $f$, but its second derivative is not uniformly $2$, but oscillates between $0$ and $4$ with exponentially growing period. This oscillation is not visible in ordinary plots.

For this example, we can demask the oscillations by considering a log-log-plot:

log-log-plot of f and g up to 200,000

Of course, this does not help, in general; for example, we might have a doubly exponential period ...

$\endgroup$
12
$\begingroup$

A nice example is Brzozowski's deeply magical minimal DFA algorithm. Given a finite automaton $N = (Q, S \subseteq Q, F \subseteq Q, R \subseteq Q \times \Sigma \times Q)$, we can compute a minimal deterministic finite automaton from it:

$$ \mathrm{Minimize} : \mathrm{NFA \to DFA} = \mathrm{Determinize\circ Reverse \circ Determinize \circ Reverse} $$

This is obviously a worst-case exponential time algorithm, since it can take a nondeterministic automaton and give you a deterministic one (or even more obviously, it calls the subset construction twice).

However, if you give Brzozowski's algorithm a DFA as an input, on many common kinds of input it can compete with and often outperform specialized DFA-minimization algorithms (which are typically $O(n^2)$, or $O(n \log(n))$ if you are hard-core and implement Hopcraft's algorithm).

This touches the "plot" part of the "plot inspection heuristic" --- we have to choose which points to sample when drawing the plot, and you can fool a naive plot if you don't choose your points carefully. This is also true for other examples, such as Quicksort and the Simplex algorith, but for pedagogy I prefer this algorithm to those two.

Quicksort's difference is "only" quadratic versus log-linear, which is less spectacular than a polynomial/exponential difference. The simplex algorithm does have a similarly spectacular difference, but it's analysis is considerably more complicated than Brzozowski's algorithm.

(Also, I feel that Brzozowski's DFA minimization algorithm is much less well-known than it deserves to be, but of course that's a matter of taste.)

$\endgroup$
  • $\begingroup$ Sorry, but I don't quite see the connection to interpreting function plots. $\endgroup$ – Raphael Mar 29 '12 at 15:27
  • 3
    $\begingroup$ I assume you would do something like plot performance versus instance size for a sampling of instances -- and Brzozowski's algorithm would "look" polynomial unless you chose instances to make it exponential time. $\endgroup$ – Neel Krishnaswami Mar 29 '12 at 17:13
  • 1
    $\begingroup$ I see. That is certainly an issue when benchmarking algorithms and plotting average runtimes, i.e. an issue of plotting the right data. When I posed the question I was only thinking about interpreting the plot correctly, which is another beast entirely. Can you please add this perspective to the answer? $\endgroup$ – Raphael Mar 29 '12 at 17:52
  • $\begingroup$ You'd have the same problem for all algorithms that have different average and worst case behaviour; Quicksort and Simplex come to mind. $\endgroup$ – Raphael Mar 29 '12 at 18:02
8
$\begingroup$

The mathematical technique of curve fitting can be used to provide an infinite number of answers to your question. Given a curve and a range, one can readily find a polynomial that fits the curve to any degree of accuracy. This example from wikipedia shows how a sin wave can be fairly accurately fitted with a forth order polynomial (the blue curve).

enter image description here

I could use higher order polynomials, and fool the plot inspection heuristic even better than this graph does.

$\endgroup$
  • 2
    $\begingroup$ That's true. It also has an artificial taste, though. Sure I can generate counter-examples for students this way but I don't see the more sceptical being convinced by it. Are there "natural" occurrences of this phenomenon (i.e. polynomial functions of higher degree that can be mistaken for other functions) where misinterpretation is "fatal"? $\endgroup$ – Raphael Mar 29 '12 at 9:17
  • $\begingroup$ I know that it isn't the answer you're looking for. $\endgroup$ – Dave Clarke Mar 29 '12 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.