Is 2^(2n) = O(2^n)
Solution 1
Note that
2^{n+1} = 2(2^{n})and
2^{2n} = (2^{n})^{2}
From there, either use the rules of BigO notation that you know, or use the definition.
Solution 2
First case is obviously true  you just multiply the constant C in by 2.
Current answers to the second part of the question, look like a handwaving to me, so I will try to give a proper math explanation. Let's assume that the second part is true, then from the definition of bigO, you have:
which is clearly wrong, because there is no such constant that satisfy such inequality.
Solution 3
Claim: 2^(2n) != O(2^n)
Proof by contradiction:
 Assume: 2^(2n) = O(2^n)
 Which means, there exists c>0 and n_0 s.t. 2^(2n) <= c * 2^n for all n >= n_0
 Dividing both sides by 2^n, we get: 2^n <= c * 1
 Contradiction! 2^n is not bounded by a constant c.
Therefore 2^(2n) != O(2^n)
Solution 4
I'm assuming you just left off the O() notation on the left side.
O(2^(n+1)) is the same as O(2 * 2^n), and you can always pull out constant factors, so it is the same as O(2^n).
However, constant factors are the only thing you can pull out. 2^(2n) can be expressed as (2^n)(2^n), and 2^n isn't a constant. So, the answer to your questions are yes and no.
Solution 5
2^{n+1} = O(2^{n}) because 2^{n+1} = 2^{1} * 2^{n} = O(2^{n}). Suppose 2^{2n} = O(2^{n}) Then there exists a constant c such that for n beyond some n_{0}, 2^{2n} <= c 2^{n}. Dividing both sides by 2^{n}, we get 2^{n} < c. There's no values for c and n_{0} that can make this true, so the hypothesis is false and 2^{2n} != O(2^{n})
JuggernautDad
Updated on July 15, 2022Comments

JuggernautDad 3 months
Is 2^{(n+1)} = O(2^{n})?
I believe that this one is correct because
n+1 ~= n
.
Is 2^{(2n)} = O(2^{n})?
This one seems like it would use the same logic, but I'm not sure.