3
$\begingroup$

What do we mean by running time of algorithms? when we say running time of bubble sort is O($n^2$), what are we implying? Is it possible to find the approximate time in minutes/seconds from the asymptotic complexity of the algorithm? If so, how ?

$\endgroup$
8
$\begingroup$

What do we mean by running time of algorithms?

Depends on who is talking. It can mean everything from actual time in seconds to execution count of some asymptotically dominant instruction. Things get muddied further by widespread overuse of Landau notation.

Also, one typically distinguishes at least worst, average and best case.

when we say running time of bubble sort is $O(n^2)$, what are we implying?

Here we use that the actual running time is in $\Theta$ of the execution count of an asymptotically dominant operation. We can rigorously show that Bubblesort takes $\Theta(n^2)$ comparisons (in fact, we can get the exact number for worst-, best- and average case), that all other operations happen only $O(n^2)$ often, and thus the real running-time has to be in $\Theta(n^2)$ as well.

That assumes that our machine model (usually RAM) and the real machine differ only by constant factors (unknown to us). If you analyzed formally on the TM model, you could not carry over Landau bounds as easily. In general, converting between (reasonable) models can add a polynomial factor.

Is it possible to find the approximate time in minutes/seconds from the asymptotic complexity of the algorithm?

No, not at all. Assuming that by "asymptotic complexity" you mean a Landau bound on the runtime function $T$,

  1. you only know the behaviour of T for $n \geq n_0$ for some $n_0$ that may be larger than anything you ever see in inputs;
  2. you only know the behaviour up to a constant factor $c$;
  3. you only know the type/degree of the leading terms but lower terms can be significant (i.e. the absolute error of your bound can tend to infinity, even if you have a tight estimate of the constant factor of the leading term).

Even if you knew $n_0$, lower-order terms and all constant factors,

  1. these bounds are usually not tight and
  2. the analysis gives you the execution of some operations, not actual time.

The only way to use formal analysis for predicting actual running times is

  1. analysing the execution counts for all statements,
  2. analysing up up to small error terms, and
  3. know how many (nano)seconds each statement takes.

Sometimes we can do 1. and 2. but 3. is very, very tough for real machines -- which is why everybody in TCS analyses on clean machine models.

$\endgroup$
-3
$\begingroup$

Asymptotic complexity is not used to find actual running times of algorithms but as a comparison tool to find out which algorithm is more efficient. When you say $Algorithm_1$ is O(nlogn) as opposed to $Algorithm_2$ which is O($n^2$) you simply mean $Algorithm_1$ is a better algorithm in terms of run time complexity.

Now coming to your question about finding actual time taken here's a possible solution.
Say your algorithm's running time is approximated as a function of the form T(n)=a$n^2$, now you know beforehand that T(100)=10 seconds. Hence you substitute T(100) and get $a*10000=10$, or $a=1/1000$.
Now you want to find out the running time when the i/p size is 200(say). You just substitute 200 in T(n)=$1/1000$*$a^2$ and get the required time in seconds.

$\endgroup$
  • 3
    $\begingroup$ "you simply mean heap sort is a better sorting algo. Period." Not necessarily. "Better" is very dependent on circumstances. For example, it might be very important to sort the data without using much auxilliary storage. In that case, bubble sort is much better, since it's an in-place sort, even though it's slower. $\endgroup$ – David Richerby Apr 18 '16 at 19:46
  • $\begingroup$ Correct, but didn't go into much technicality here as the question asked is to find actual running time .For that just needed to make a point. So merely saying one is better than the other serves the purpose. $\endgroup$ – Sukanta Chatterjee Apr 18 '16 at 19:54
  • $\begingroup$ Making an absolute-sounding, yet vague, unquantifiable statement rarely serves any purpose. $\endgroup$ – David Richerby Apr 18 '16 at 23:49
  • $\begingroup$ Did an edit. Is it right? $\endgroup$ – Sukanta Chatterjee Apr 19 '16 at 5:10
  • $\begingroup$ Well, now it's almost a tautology. It's hard to see how you're not just saying "Having better running time means having better runing time." $\endgroup$ – David Richerby Apr 19 '16 at 5:16

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.