2^(2n) = O(2^n) ; true or false?

[hystaspes]

Hi there,

My question is about 2^(2n) = O(2^n) ; is it true or false?

and we know that:
f(n) = O(g(n)) if positive integers c and n0 exist such that for every n >= n0 : f(n) <= c*g(n)

Based on the definition, I'm thinking the above statement is false because we can't find any n0 and c that satisfies 2^(2n) <= c*2^n

BUT, I'm not sure if I'm right or wrong, I'm not sure where should I put that c. should I write:

2^(2n) <= c*2^n
Or
2^(2n) <= 2^(c*n) ?

Thank you for your help

[histrungalot]

I think this is correct but what do you think?
It would have to be 2^2n <= c*2^n, because its f(x) = O(g(x)). Here f(x) = 2^2n and g(x) = 2^n.

2^2n <= c*2^n
Check it out, if true
log2(2^2n) <= log2(c*2^n) for some n > n0
2n <= log2(c)+n
2n-n <= log2(c)
n <= log2(c) <---- FALSE
Because c is a fixed number, but n is unbounded. Therefore this can not be true for all n > n0 and c.
Ref
http://en.wikipedia.org/wiki/Big_O_notation

[pyTony]

More simply let's see what it would mean if the statement was true:
2 ^(2n) = O(2^n)
2 ^ n * 2 ^ n = c * 2 ^ n
2 ^ n = c which is obviously wrong as it means n is constant.

[hystaspes]

thank you so much for your help :)

now, my last question is when should I multiply c in the exponent? is it only if the O(g(n)) is the exponent? like: 2^(2n) = 2^O(n) --> 2^(2n) <= 2^(c*n)

I think it's wrong to write 2^(2n) = O(2^n) --> 2^(2n) <= 2^(c*n) (but I'm not sure).

Thanks again for your replies :)

[histrungalot]

I would say yes if the g(n) is the exponent, then the c could multiply in the exponent. THAT SAID I don't think 2^O(n) is a valid big O notation. Just remember it c*g(n), so whatever is in the O(whatever) it is c*whatever.

[Rashakil Fol]

So just to summarize: histrungalot's first reply is wrong, pyTony's reply is right, histrungalot is wrong to say that 2^O(n) is invalid notation.

now, my last question is when should I multiply c in the exponent?

What do you mean? Why would you multiply something into an exponent? is it only if the O(g(n)) is the exponent? like: 2^(2n) = 2^O(n) --> 2^(2n) <= 2^(c*n)

It is correct to say that 2^(2n) is in the set 2^(O(n)), or, informally, 2^(2n) = 2^(O(n)). It is correct to say that there exists some c such that 2n <= c*n, for positive n. Because the function x -> 2^x is monotonically increasing, it follows that 2^(2n) <= 2^(c*n) for some c, if n is positive.I think it's wrong to write 2^(2n) = O(2^n) --> 2^(2n) <= 2^(c*n) (but I'm not sure).

This question is nonsensical, because 2^(2n) = O(2^n) is false. 2^(2n) is not in the set O(2^n).

Generally speaking, the notation 2^O(n) is worthless. All it tells you is that you have at most _some_ kind of exponential function. 2^O(n) is equivalent to 4^O(n), but O(2^n) is not the same as O(4^n). The only time I've seen it useful to put O notation inside an exponential is when giving the runtime of Furer's algorithm, which, if I remember correctly, is O(n * log(n) * 2^O(log^*(n))). log^* is the iterated logarithm function.

This means that for some constant k that could be arbitrarily large, the complexity might be O(n * log(n) * (2^(log^*(n)))^k). It's notable that 2^(log^*(n)) grows slower than log(log(n)).

Another example of O notation inside an exponential would be

O(2^O(log(n))). In this case the function grows slower than 2^(k*log2(n)) for some constant k. (Obviously k1*log(n) = k*log2(n) if k = k1*log(2), that's just a choice of scaling.) This reduces to O(n^k) for some k, so it's just a way of saying the function's polynomial.

Another example of an exponent with big O in the argument would be O(2^O(log(log(n)))). Likewise this reduces to O(2^(k*log2(log(n)))) for some k. Which reduces to O((log(n))^k) for some k. So we know the function is sublinear, in that case. Saying "2^O(...)" is useful so that we don't have to keep qualifying our statements with "for some k."