大 O 表示法：证明 f(n) ∈ O(n^4)？

Question

这是一个java练习册问题。我一直在寻找一种方法来解决但没有成功。

我们f(n) = 100n^4+ 5000n+ 3. Is f(n)∈ O(n^4)?如果是，则通过提供适当的正的常数证明你的答案c和n_0。

我相信答案是否定的，但我需要有关如何解决问题的指导。

先感谢您！

Answer 1

你可以用这种方式证明100n^4 +5000n +3 < 5000(n^4 +n+1) 对于所有 n>1 ...(1)5000(n^4 +n+1) < 5000(n^4 + n^4 + n^4) 对于所有 n>1 ... (2)这意味着100n^4 +5000n +3 < 15000(n^4) 对于所有 n>1所以，证明 100n^4 +5000n +3 是 O(n^4)

Answer 2

Let&nbsp;f(n)&nbsp;=&nbsp;100n^4+&nbsp;5000n+&nbsp;3简单地说，我们将删除所有常量Let&nbsp;f(n)&nbsp;=&nbsp;n^4+&nbsp;n我们将使用一些算法来评估：Let&nbsp;f(n)&nbsp;=&nbsp;n^4+&nbsp;n&nbsp;=&nbsp;n(n^3+1)我们将继续删除常量Let&nbsp;f(n)&nbsp;=&nbsp;n(n^3+1)&nbsp;=&nbsp;n*n^3&nbsp;=&nbsp;n^4所以最后f(n)∈&nbsp;O(n^4)如果我误解了什么，请通知我，我还在学习算法。