patternMinor
What is running time of an algorithm?
Viewed 0 times
algorithmrunningtimewhat
Problem
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 ?
Solution
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$,
Even if you knew $n_0$, lower-order terms and all constant factors,
The only way to use formal analysis for predicting actual running times is
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.
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$,
- 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;
- you only know the behaviour up to a constant factor $c$;
- 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,
- these bounds are usually not tight and
- 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
- analysing the execution counts for all statements,
- analysing up up to small error terms, and
- 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.
Context
StackExchange Computer Science Q#56133, answer score: 8
Revisions (0)
No revisions yet.