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 一样快。
如有必要，所有这些陈述都可以从定义中得到证明，请让我知道您是否希望看到一两个例子。