對於以下每個函數f找到一個簡單函數g，使得f（n）=Θ（g（n））（Skiena的算法設計手冊）

Question

我正在從Skiena算法設計手冊中進行練習，我不確定約2.30。你會說我的解決方案是正確的嗎？ a link to the screenshot of the exercise

1. 4^N
2. ň
3. 的log（n^20）
4. （0.99）^ n的

非常感謝你的幫助！

Answer 1

數字1和4是正確的，而2和3是不正確的。

• 2：應該是n log n，因爲log n > (constant)。
• 3：應該是(log n)^10，因爲log (n^20) = 20 log n，它比較小。