Are 2 ^ n and 4 ^ n in the same Big- complexity class ??

Question

Is 2 ^ n = Θ (4 ^ n)?

I am sure that 2 ^ n is not in Ω (4 ^ n), therefore not in Θ (4 ^ n), but my university professor says that it is. This confused me, and I could not find a clear answer on Google.

Answer 1

2^n NOT big-theta (Θ) 4^n , this is because 2^n NOT big-omega (Ω) of 4^n .

By definition, we have f(x) = Θ(g(x)) if and only if f(x) = O(g(x)) and f(x) = Ω(g(x)) .

Statement

2^n is not Ω(4^n)

Proof

Assuming 2^n = Ω(4^n) , then, by the definition of big-omega, there exist constants c > 0 and n0 such that:

2^n ≥ c * 4^n for all n ≥ n0

Rebuilding the inequality, we have:

(1/2)^n ≥ c for all n ≥ n0

But note that as n → ∞ left side of the inequality tends to 0 , while the right side is equal to c > 0 . Therefore, this inequality cannot hold for all n ≥ n0 , so we have a contradiction! Therefore, our assumption at the beginning should be incorrect, therefore 2^n is not Ω(4^n) .

Update

As mentioned by Ordous , your teacher can refer to the EXPTIME complexity class, in this coordinate system, both 2^n and 4^n are in the same class. Also note that we have 2^n = 4^(Θ(n)) , which could also mean your tutor.

Answer 2

Yes: one way to see this is to mark 4^n = 2^(2n) . So 2^n has the same complexity as 4^n (exponential), because n and 2n have the same complexity (linear).

In conclusion, the basics here do not affect complexity; all that matters is that exhibitors have the same complexity.

Edit : this answer shows that 4^n and 2^n are of the same complexity, and not that 2^n is a big theta 4^n : you are right that this is not so, since there is no constant k such that k*n^2 >= n^4 for all n . At some point, n^4 will overtake k*n^2 . (Thanks to @ chiwangc / @ Ordous for highlighting the differences in their answer / comment.)

Answer 3

Yes. Both have exponential complexity.