Why is O(n^2) the same as Θ(n^2)?

Question

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.

I don't think this is the right place for this question. Try programmers.stackexchange.com — Matt Grande, Oct 21 '13 at 19:58
possible duplicate of [What is the difference between Θ(n) and O(n)?](http://stackoverflow.com/questions/471199/what-is-the-difference-between-n-and-on) — Pascal Cuoq, Oct 21 '13 at 19:59
`f` is Big-theta(f) if it is both big-o(f) and big-omega(f) at the same thime. — loki, Oct 21 '13 at 19:59

templatetypedef · Answer 1 · 2013-10-21T20:43:49.663

1

That's not true. For example, n = O(n²) (choose c = 1, n₀ = 0) but is not Θ(n²) (because lim_n→∞ n / n² = 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!

edited Oct 21 '13 at 20:43

answered Oct 21 '13 at 19:57

templatetypedef

362,284
104
897
1,065

score 1 · Answer 2 · edited Oct 21 '13 at 20:06

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.

edited Oct 21 '13 at 20:06

glglgl

89,107
13
149
217

answered Oct 21 '13 at 19:58

Ken Wayne VanderLinde

18,915
3
47
72

@glglgl: For future reference, how would I type a Θ on SO? – Ken Wayne VanderLinde Oct 21 '13 at 20:16
Copy & paste from somewhere else, e. g. the linked question. – glglgl Oct 21 '13 at 20:21

score 0 · Answer 3 · edited May 23 '17 at 11:57

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.

edited May 23 '17 at 11:57

Community

1
1

answered Oct 21 '13 at 19:58

Benjamin Trent

7,378
3
31
41

Why is O(n^2) the same as Θ(n^2)?

3 Answers3