11
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 13, 2022 at 15:59
  • 4
    $\begingroup$ 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. $\endgroup$
    – Bakuriu
    Sep 13, 2022 at 19:02
  • 2
    $\begingroup$ 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. $\endgroup$
    – Cort Ammon
    Sep 14, 2022 at 0:46
  • $\begingroup$ I agree with @Peter Cordes. Perhaps that point should be responded to or even an edit made? $\endgroup$ Sep 14, 2022 at 13:22
  • 1
    $\begingroup$ @PeterCordes yes i meant n^2 $\endgroup$ Sep 15, 2022 at 13:10

3 Answers 3

9
$\begingroup$

Yes. Your understanding is correct on all points!

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
3
  • 4
    $\begingroup$ 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. $\endgroup$
    – Stef
    Sep 13, 2022 at 8:17
  • 3
    $\begingroup$ 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. $\endgroup$ Sep 13, 2022 at 15:46
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Sep 15, 2022 at 13:53
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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