How to prove this statement of big o notation?
How to prove thi开发者_开发技巧s:
- 4n = O(8n)
- 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.
精彩评论