2

Today our professor mentioned that O(n^2) is the same as Θ(n^2).

I did not understand the explanation for that and I could not find something on the internet. Can please somebody explain it to me?

Thank you very much.

3

3 Answers 3

1

It is not the same. O is about upper bounds, Ω is about lower bounds, and Θ is about both upper and lower bounds.

As an example, a function f(n) = n is O(n^2), but not Θ(n^2), since we can't bound f from below by a multiple of n^2.

2
  • @glglgl: For future reference, how would I type a Θ on SO? Oct 21, 2013 at 20:16
  • Copy & paste from somewhere else, e. g. the linked question.
    – glglgl
    Oct 21, 2013 at 20:21
1

That's not true. For example, n = O(n2) (choose c = 1, n0 = 0) but is not Θ(n2) (because limn→∞ n / n2 = 0). I suspect that you either misheard the instructor, they misspoke, or they were talking about a specific context in which it was true that didn't generalize.

Hope this helps!

0

Big O only gives an upper bound. Θ gives the lower bound as well. This SO Question should prove helpful. Your professor would be right if he said the reverse. As stated in the referenced question:

Θ(f(n)) is also O(f(n)) but not the other way around.

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.