proof - 帮忙证明 Big Omega？

Question

我在求解证明时遇到问题。其中 t(n) <= cn^1.6，c 为常数。总的来说，Big Omega 与 Big O 相反，它是最好的情况，寻找下界。所以存在一个 c 和 n0 使得 n >= n0。但我不确定如何将其应用于证明以及如何操纵方程中的常数来找到 c 和 n0 并证明 t(n) 是 Omega(n^1.6)。

t(n) = (n-3logn)^1.6 + 5n^1.5 + 7 是 Omega(n^1.6)

谁能提供一些关于如何解决此类问题的见解？提前致谢!

此外，我没有收到任何来自下方评论的批评，这不是家庭作业问题，而是一组练习中的示例，以便有人更容易解释此类问题背后的一般概念问题。

Answer 1

Big-Omega 的定义:f(n)=Omega(g(n)) 当且仅当常数 C 和 K 存在使得对于所有 n > K，f(n) > C * g(n)

换句话说，你需要能够说出这样的话:“我选择 C ​​= 5，现在对于所有 n > 1000，f(n) > 5 * g(n)，所以有。”

现在让我们看看您的问题。

t(n) = (n-3logn)^1.6 + 5n^1.5 + 7 is Omega(n^1.6)

C * n^1.6 < (n-3logn)^1.6 + 5n^1.5 + 7

除以 n^1.6

C < ((n-3logn)/n)^1.6 + 5n^-0.1 + 7/n^1.6
C < (1 - 3logn/n)^1.6 + 5n^-0.1 + 7/n^1.6

那么让我们一一看一下这三个术语(当然，需要更正式的证明，但这些很简单)。

1. (1 - 3logn/n)^1.6 = (1 - 0.smth)^1.6 = (0.smth)^1.6 < 1 for n > 2
2. 5n^-0.1 = 5/n^0.1 = 5/smth greater than 1 < 5 for n > 2
3. 7/n^1.6 = 7/smth large < 1 for n > 2

所以我们看到对于任何 n > 2，C < 1 + 5 + 1 = 7

现在你可以说“我选择 C=7，对于任何 n > 2，C*n^1.6 < ...”