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 s开发者_C百科ure.

---

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 big-O, you have:

which is clearly wrong, because there is no such constant that satisfy such inequality.

---

Claim: 2^(2n) != O(2^n)

Proof by contradiction:

1. Assume: 2^(2n) = O(2^n)
2. Which means, there exists c>0 and n_0 s.t. 2^(2n) <= c * 2^n for all n >= n_0
3. Dividing both sides by 2^n, we get: 2^n <= c * 1
4. Contradiction! 2^n is not bounded by a constant c.

Therefore 2^(2n) != O(2^n)

---

Note that

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.

---

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.

---

2ⁿ⁺¹ = O(2ⁿ) because 2ⁿ⁺¹ = 2¹ * 2ⁿ = O(2ⁿ). Suppose 2²ⁿ = O(2ⁿ) Then there exists a constant c such that for n beyond some n₀, 2²ⁿ <= c 2ⁿ. Dividing both sides by 2ⁿ, we get 2ⁿ < c. There's no values for c and n₀ that can make this true, so the hypothesis is false and 2²ⁿ != O(2ⁿ)

---

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.

---

We will use=> a^(m*n) = (a^m)^n = (a^n)^m now,

2^(2*n) = (2^n)^2 = (2^2)^n

so,

(2^2)^n = (4)^n

hence,

O(4^n)

Obviously,

rate of growth of (2^n) < (4^n)

---

Let me give you an solution that would make sense instantly.

Assume that 2^n = X (since n is a variable, X should be a variable), then 2^(2n) = X^2. So, we basically have X^2 = O(X). You probably already know this is untrue based on a easier asymptotic notation exercises you did.

For instance:

• X^2 = O(X^2) is true.
• X^2+X+1 = O(X^2) is also true.
• X^2+X+1 = O(X) is untrue.
• X^2 = O(X) is also untrue.

Think about polynomials.