开发者

How to prove this statement of big o notation?

How to prove thi开发者_开发技巧s:

  1. 4n = O(8n)
  2. 8n = O(4n)?

So what are the C and n0 values for both cases?


EDIT: I tried to clarify I bit more ...

1. For a proof (see formal definition of Big-O) we have to find any C and n0, that 4n <= C * 8n for all n > n0. So - to prove your case 1 it is all about finding an example for these two values. We will try ... the equation I just quoted from wikipedia says:

f(n) = O(g(n))

if and only if there exists a positive real number C and a real number n0 such that

|f(n)| <= C * |g(n)| for all n > n0

where f(n) = 4n and g(n)=8n

4^n    <= C * 8^n
4^n    <= C * 2^n * 4^n
1      <= C * 2^n

So we choose C to be 1 and n0 to be 1, too. The equation is true -> case 1 proven.

2. Since I guess, that this is homework - you should give it a try yourself - I can help you a bit more, as soon as you provide results of your own tries.
Hint: just try to find a C and a n0 there, too - maybe you can prove, that there never exists any pair of C and n0 for the equation ... ^^


From what I remember of the law of logarithms:

logb(xy) = (y)logb(x)

I think this is a good starting point. I'm not going to finish because this is a homework assignment. ;)

UPDATE:

The more I look at it, the more I think that something is missing from the original question. Define what C and n0 are, for starters.

0

上一篇:

下一篇:

精彩评论

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

最新问答

问答排行榜