3
$\begingroup$

I have an algorithm and I determined the asymptotic worst-case runtime, represented by Landau notation. Let's say $T(n) = O(n^2)$; this is measured in number of operations.

But this is the worst case, how about in average? I tried to run my algorithm 1000 times for each $n$ from $1$ to $1000$.I get another graph which is the average running time against $n$ but measured in real seconds.

Is there any possible way to compare these figures?

Improve this question
$\endgroup$
5
  • $\begingroup$ absolutely they can be combined for an interesting/insightful graph & very worthwhile undergraduate exercise (dont know why it is so rare), just graph two lines on same graph, but dont misinterpret its meaning. # operations generally correlates roughly with some unknown multiplicative constant with asymptotic worst case (try estimating/calculating/curve fitting your constant!). gnuplot is a good widely used open pkg, what graph software are you using? try visiting chat for more hints $\endgroup$
    – vzn
    Commented Feb 2, 2014 at 15:55
  • $\begingroup$ I think my answer outlines why this is bad advice. The main reason is that you can not tell whether the graph is insightful or misleading. $\endgroup$
    – Raphael
    Commented Feb 2, 2014 at 16:34
  • $\begingroup$ @Raphael already +1 on answer; think you have valid pts but more an issue with statistics & scientific quantification than CS in particular eg how to lie with graphs. graphing & its correct interpretation is a key part of scientific quantification/presentation methods etc $\endgroup$
    – vzn
    Commented Feb 2, 2014 at 17:14
  • $\begingroup$ That is all well if you do natural science with statistical methods. In the context of algorithm analysis, however, we usually work mathematically. Whether that is good/sufficient for the field is certainly debatable, but as soon as Landau symbols pop up, we are in the mathematical world and should stay there. (Note that a statement $f \in O(n)$ is not scientific in the sense that it can not be falsified by experiments.) $\endgroup$
    – Raphael
    Commented Feb 2, 2014 at 17:20
  • $\begingroup$ agreed; graphs are an intuitive picture of the mathematical world. there is also an apparent left brained vs right brained teaching/pedagogical style with graphs fitting more into the latter & notation more the former. both need to be leveraged/combined for insight. am just agreeing with/reiterating a key premise on the value of graphing stated by elite member DC elsewhere =) ... there is room for different povs/"schools of thought" on this subj... $\endgroup$
    – vzn
    Commented Feb 2, 2014 at 17:23

1 Answer 1

Reset to default
4
$\begingroup$

You can't, not really, for three reasons:

  1. Number of operations and runtime do not compare well; too many factors (typically) left out in analysis influence actual runtime.
  2. Asymptotic results (which hold in the limit) and a finite sets of observations do not compare.
  3. Landau classes don't compare with "exact" functions. For instance, if you have $f \in O(n^3)$ and $g(n) = 3n^2$, you have no idea which grows faster.

All hope is not lost, though. With some additional work you can get to reliable statements.

  • Perform an (asymptotic) average-case analysis. That is, assume a random distribution on the input set and calculate the expected number of executed operations. That can be tough, but if you succeed you can compare the result to your worst-case asymptotic. (Note that you may need $\Theta$ to make meaningful statements.)

  • If you can, improve your analysis to yield constant factors (not only $\Theta$). That way, you can separate, say, a $2n^2 + 5n$ worst-case from $1.5n^2 - 3 \log n$ average-case.

  • Run the program for worst-case instances (you should know them from your WC-analysis) and compare the real measurements with the average case.

    Note: This can only provide guesses for asymptotic behaviour.

  • Alternatively, run the program average and worst-case instances but count statements. That gives you more reliable measurements and removes platform-dependent artifacts from consideration. Still, you get only guesses for asymptotics.

Bottom line, you have to have the same "kind" of statement for both worst- and average-case if you want to compare them.

Improve this answer
$\endgroup$
1
  • $\begingroup$ There is some current research on using finite samples for the prediction of asymtotic average-case runtimes. It's exact under certain assumptions, and a decent heuristic otherwise. (Full disclosure: I'm a member of this group.) $\endgroup$
    – Raphael
    Commented Feb 2, 2014 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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