3
$\begingroup$

If an algorithm has running time of $\Theta(n^2)$, is it possible to have a best-case running time of $\Omega(n)$? Or is the fastest running time only $c n^2$ for some constant factor $c$?

$\endgroup$
  • 1
    $\begingroup$ Maintain a clear separation in your mind between the case (best, worst, average, etc.) and the bound ($\Theta$, $O$, $\Omega$, etc.) If $\Theta(n^2)$ is a bound on the worst-case or average-case, then you may have a best-case bound of $\Omega(n)$. If $\Theta(n^2)$ is a bound on the best case, the. $cn^2$ is as good as you can do, and no $\Omega$ bound is possible. $\endgroup$ – Patrick87 Oct 27 '14 at 15:53
  • $\begingroup$ Beyond the interpretation of "running time", I think this is a perfect duplicate of this question. Also, I'm not sure if $\Omega$ is what you want there (Best-Case in $O(n)$ would be interesting); you might want to check this question. $\endgroup$ – Raphael Oct 27 '14 at 16:49
2
$\begingroup$

Normally, it's the worst-case running time that is given but one should never say just "running time" since it could be anything – best-case, worst-case, average case according to some probability distribution, amortized, ...

If the worst-case running time is $\Theta(n^2)$ all you can say about the best case is that it can't be worse than the worst case, so the best case is $O(n^2)$. So, yes, the best case could be $\Omega(n)$.

$\endgroup$
  • $\begingroup$ Thanks, your explanation is very accessible for a beginner to computer science. $\endgroup$ – MNRC Oct 27 '14 at 18:01
3
$\begingroup$

There are two possible interpretations for "running time of an algorithm". The first interpretation is the worst-case running time, depending on some parameters such as the input length $n$. The second interpretation is that the running time is some bound that holds for all inputs with the given parameters. When we give a big $O$ estimate, both interpretations amount to the same thing: if an algorithm has a running time of $O(n^2)$, then this is both a worst-case bound and a bound which is valid for all inputs of length $n$.

What is then the interpretation of $\Theta(n^2)$ in your case? It's hard to say without more details, and could depend on the context. If it's a worst-case bound then the meaning is "there is a family of inputs for which the algorithm runs in $\Omega(n^2)$ time". If it's a global bound then the meaning is "the algorithm runs in $\Omega(n^2)$ time on all inputs". Out of these two possible interpretations, the first seems slightly more likely, but others may hold different opinions.

$\endgroup$

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