大 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 f(n) = 100n^4+ 5000n+ 3

简单地说，我们将删除所有常量

Let f(n) = n^4+ n

我们将使用一些算法来评估：

Let f(n) = n^4+ n = n(n^3+1)

我们将继续删除常量

Let f(n) = n(n^3+1) = n*n^3 = n^4

所以最后

f(n)∈ O(n^4)

如果我误解了什么，请通知我，我还在学习算法。