# Time Complexity $\Theta$ vs. $\Omega$ [duplicate]

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$?

• 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. Oct 27 '14 at 15:53
• 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.
– Raphael
Oct 27 '14 at 16:49

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