Simple Big O with lg(n) proof

Posted by halohunter on Stack Overflow See other posts from Stack Overflow or by halohunter
Published on 2010-03-19T17:07:18Z Indexed on 2010/03/19 17:11 UTC
Read the original article Hit count: 187

Filed under:
|

I'm attempting to guess and prove the Big O for:

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

I guess that big O is n^3 as it is the term with the largest order of growth

However, I'm having trouble proving it. My unsuccesful attempt follows:

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

But this can't be right because c must be constant. What am I doing wrong?

© Stack Overflow or respective owner

Related posts about big-o

Related posts about algorithm