Is 2^(2n) = O(2^n)
Is 2(n+1) = O(2n)?
I believe that this one is correct because n+1 ~= n.
Is 2(2n) = O(2n)?
This one seems like it would use the same logic, but I'm not sure.
2n+1 = 2(2n)and
22n = (2n)2
From there, either use the rules of Big-O notation that you know, or use the definition.
First case is obviously true - you just take away the constant
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 big-O, you have:
which is clearly wrong, because there is no such constant that satisfy such inequality.
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.
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)
To answer these questions, you must pay attention to the definition of big-O notation. So you must ask:
is there any constant C such that 2^(n+1) <= C(2^n) (provided that n is big enough)?
And the same goes for the other example: is there any constant C such that 2^(2n) <= C(2^n) for all n that is big enough?
Work on those inequalities and you'll be on your way to the solution.
2n+1 = O(2n) because 2n+1 = 21 * 2n = O(2n). Suppose 22n = O(2n) Then there exists a constant c such that for n beyond some n0, 22n <= c 2n. Dividing both sides by 2n, we get 2n < c. There's no values for c and n0 that can make this true, so the hypothesis is false and 22n != O(2n)