# Is Big-Theta a more accurate description of worst case run time than Big-O?

Question I was asked: Does it make a difference if I say "The worst case run time is $$O(n^2)$$ vs the worst case run time is $$\Theta(n^2)$$?"

To me, the only difference is that when we say $$O(n^2)$$, the function may also be $$O(n)$$, we do not know. But when we say $$\Theta(n^2)$$, we know for a fact the function is $$O(n^2)$$ and $$\Omega(n^2)$$, because it is bounded by $$c_1n^2\leq f(n)\leq c_2n^2$$ (correct me if I am wrong).

Therefore, can we not say that $$\Theta(n^2)$$ gives us a more accurate (or at least equal) sense of worst-case run time than $$O(n^2)$$?

• In your last sentence, did you really mean O(n), not O(n^2)? O(n) is incompatible with Theta(n^2) (unlike vice versa), so no you can't say that. But that sentence construction in English is saying you think we can say that. Sep 13, 2022 at 15:59
• Keep in mind that not all algorithms can have "Theta" complexity. There are algorithms that vary in complexity. Those can only be described with Big-O complexity. In that case to have a better understanding on the performance you want to define a statistical distribution of the inputs and then compute the average complexity. That complexity can be described in "theta" terms... unfortunately computing the average complexity is often really difficult/time consuming or even intractable. Sep 13, 2022 at 19:02
• One minor thing that may help. When we say that something $O(n^2)$ or $\Theta(n^2)$ we typically have to prove it. Sometimes the proof for $\Theta$ is natural, sometimes its harder. And often the O is all we really need for our proofs, so we are often lazy in that regard. Sep 14, 2022 at 0:46
• I agree with @Peter Cordes. Perhaps that point should be responded to or even an edit made? Sep 14, 2022 at 13:22
• @PeterCordes yes i meant n^2 Sep 15, 2022 at 13:10

Yes. Your understanding is correct on all points!

O(f(n)) is also used when there is no simple function that your runtime is close to. For example: Find the smallest prime factor of n by trial division, finishing when a factor is found: There are O(n^1/2) tests if you divide by all integers up to the square root of n. But for even n there is only one test, and similar if n has any small factor.

So you can’t give any reasonable Theta unless you say f(n) = Theta(f(n)) which is true but pointless.

There is also the possibility that I can prove that a function is for example $$O(n^2)$$. I may suspect it is actually smaller, it may actually be $$O(n)$$ but I cannot prove it. Obviously in that situation I can also not prove that it is $$\Theta(n^2)$$ - because it isn't true.

• This example is a bit contrived because you used n as the value of the input, as opposed to the length of the input. If you used n as the length of the input, then there would be many different values of input for the same n, and typically one of them will achieve the worst-case.
– Stef
Sep 13, 2022 at 8:17
• Using n as the input isn't contrived. O is not a computer science concept and so length doesn't pertain to it in general. Sep 13, 2022 at 15:46
• For moderately sized numbers, giving the runtime or number of divisions relative to the number n instead of the size of the number n is more useful. And of course who says we always want to know the worst case? The average case is also very useful. Sep 15, 2022 at 13:53

You answer yourself by saying that $$\Theta$$ is the conjunction of $$O$$ and $$\Omega$$. So yes of course, $$\Theta$$ is more informative than $$O$$ alone.

Make sure anyway that you don't confuse the asymptotic behavior of the algorithm complexity, and that of its worst-case complexity.

E.g. the running-time of QuickSort is $$O(n^2)$$ and $$\Omega(n\log n)$$, while its worst-case running-time is $$\Theta(n^2)$$.