big-o - 为什么 O(n^2) 与 Θ(n^2) 相同？

Question

今天我们教授提到O(n^2)和Θ(n^2)是一样的。

我不明白对此的解释，我在互联网上找不到任何东西。请有人向我解释一下吗？

非常感谢。

Answer 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!

Answer 2

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.

Answer 3

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.