简单的大O与lg(n)证明

Question

我试图猜测并证明大O:

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

我猜大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.

你可以从那里解决.