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
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