Simple Big O with lg(n) proof
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?
For any base b, we know that there always exists an n0 > 0
such that
log(n)/log(b) < n
whenever n >= n0
Thus,
n^3 - 7n^2 + nlg(n) + 10
< n^3 - 7n^2 + n^2 + 10
when n >= n0
.
You can solve from there.
For your question, the proof of O(n^3) should look something like this:
f(n) <= n^3 + 7n^2 + nlg(n) + 10 for (n > 0)
f(n) <= n^3 + 7n^3 + nlg(n) + 10 for (n > 1)
f(n) <= n^3 + 7n^3 + n*n^2 + 10 for (n > 2)
f(n) <= n^3 + 7n^3 + n^3 + 10 for (n > 2)
f(n) <= n^3 + 7n^3 + n^3 + n^3 for (n > 3)
f(n) <= 10n^3 for (n > 3)
Therefore f(n) is O(n^3) for n > 3 and k = 10.
精彩评论