开发者

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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜