How to prove this statement of big o notation?

问题:

How to prove this:

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

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

回答1:

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 4ⁿ <= C * 8ⁿ 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) = 4ⁿ and g(n)=8ⁿ

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

回答2:

From what I remember of the law of logarithms:

log_b(x^y) = (y)log_b(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 n₀ are, for starters.