algorithm - Big-Theta 符号

Question

所以我对这一切都很陌生，并正在寻找一些关于证明 Big Theta 符号的帮助和指导。

Prove that log(3^3+ 2 + 17) = Θ(log(15^5+ 7^4 − 2))

我想简单地将双方都提高到 2 的幂，然后留下表情本身，但我并不是 100% 朝着解决方案迈出了正确的一步，老实说，我有点迷失了。

我还从符号中知道我正在寻找一个可以满足以下方程的解决方案：

c1(g(n))<=f(n)<=c2(g(n)), where c is a constant. 

标签： algorithmproof

Answer 1

容易证明：

n^2 <3n^3 + 2n + 17 < 5n^5 + 7n^4 -2 < n^6 for n > 10 
=> 2 log(n) < log(3n^3 + 2n + 17) < log(5n^5 + 7n^4 -2) < log(n^6) = 6 log(n)

由于log(3n^3 + 2n + 17)和 log(5n^5 + 7n^4 -2)都在 的常数因子之间log(n)，您可以得出结论，log(3n^3 + 2n + 17) ⊂ Θ(log(5n^5 + 7n^4 -2))反之亦然。