big-o - 如何判断两个函数的Big-Theta和Big-Omega是否相等？

Question

我有一个作业要证明这些是对还是错:

• a) 150n^3 + 43n^2 + 50^n + 3 = Ω(n^5)
• b) n^10 + 30n^8 + 80n^6 = O(n^12)
• c) 55n + 30 = O(n log n)
• d) n^4 + 4 n^3 + 6 n^2 + n log n= θ(2n)
• e) 9n^2 log n + 40n^2 + 3n = Ω(n^2 log n)

我可以对 Big-O 做 B 和 C。任何人都可以帮助解决 Big-Omega 和 Big-Theta 问题吗？

(不是寻找答案，而是学习操作方法)。

Answer 1

函数 f 是 Omega(g) 当且仅当存在 n0 和 c 大于零，且 n >= n0，f(n) >= c*g(n)。

函数 f 是 Big-Oh(g) 当且仅当存在大于零的 n0 和 c，并且对于 n >= n0，f(n) <= c*g(n)。

函数 f 是 Theta(g) 当且仅当 f 既是 Omega(g) 又是 Big-Oh(g)。

(a) 150n^3 + 43n^2 + 50n + 3 不是 Omega(n^5)，因为高阶项 150n^3 的增长速度比 n^5 渐近慢，因为幂较小。

(b) n^10 + 30n^8 + 80n^6 是 O(n^12)，因为高阶项 n^10 的增长速度比 n^5 渐近慢，因为幂较小。

(c) 55n + 30 是 O(n log n)，因为高阶项 55n 比 nlog(n) 增长得更慢，因为最终 log(n) 项变得比 55 大得多(对于具体来说，n > 2^55)。

(d) n^4 + 4 n^3 + 6 n^2 + n log n 不是 Theta(2n)，因为高阶项 n^4 比 2n 渐近增长得更快，因为幂更大。它也不是 Theta(2^n)，如果这就是您的实际意思，因为 n^4 的增长速度渐近地慢于 2^n。

(e) 9n^2 log n + 40n^2 + 3n 是 Omega(n^2 log n)，因为高阶项 9n^2log(n) 的增长速度与 n^2 log n 的渐进速度一样快.

如有必要，所有这些陈述都可以从定义中证明，如果您希望看到一两个示例，请告诉我。