你好，我已经尽力理解 big-theta，现在我得到了 Big-Oh 和 Big-Omega 证明的主要概念，但我找不到接近我练习的例子，因为我无法证明那个:
通过出示证人证明 4n^2 + 4n = Big-Theta(2n^2 + 32n)
我知道我必须为 Big-Oh 和 Big-Omega 证明它才能证明 Big-Theta，但我不知道如何开始。我的意思是右边的等式让我感到困惑。
最佳答案
通过definition of big-theta ，您需要证明存在两个常数 k1 和 k2，使得对于所有足够大的 n 值，
k1 * |2n^2 + 32n| <= |4n^2 + 4n| <= k2 * |2n^2 + 32n|
(因为您的函数对于正 n 都是正的，您可以舍弃绝对值。)只要证明每个不等式都可以单独满足就可以了。
关于algorithm - 证明 Big-Theta 符号，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5464843/