algorithm - 带 lg(n) 证明的简单大 O

Question

我正在尝试猜测和证明 Big O:

f(n) = n^3 - 7n^2 + nlg(n) + 10

我猜 big O 是 n^3，因为它是增长阶数最大的项

但是，我无法证明这一点。我不成功的尝试如下:

f(n) <= cg(n)
f(n) <= n^3 - 7n^2 + nlg(n) + 10 <= cn^3 
f(n) <= n^3 + (n^3)*lg(n) + 10n^3 <= cn^3
f(n) <= N^3(11 + lg(n)) <= cn^3

so 11 + lg(n) = c

但这不可能是正确的，因为 c 必须是常量。我做错了什么？

Answer 1

对于任何基 b，我们知道总存在一个 n0 > 0这样

log(n)/log(b) < n每当n >= n0

因此，

n^3 - 7n^2 + nlg(n) + 10 < n^3 - 7n^2 + n^2 + 10什么时候n >= n0 .

你可以从那里解决。