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
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
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.
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 :)
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.
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."
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.