Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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

I'm pretty sure that 2^n is not in Ω(4^n) thus not in Θ(4^n), but my university tutor says it is. This confused me a lot and I couldn't find a clear answer per Google.

like image 659
Nibble Avatar asked Sep 30 '14 11:09

Nibble


People also ask

Can Big O and Big Omega be the same?

Difference between Big O and Big Ω The difference between Big O notation and Big Ω notation is that Big O is used to describe the worst case running time for an algorithm. But, Big Ω notation, on the other hand, is used to describe the best case running time for a given algorithm.

Does Big Theta imply Big O?

Big-O is an upper bound. Big-Theta is a tight bound, i.e. upper and lower bound. When people only worry about what's the worst that can happen, big-O is sufficient; i.e. it says that "it can't get much worse than this".

How is Theta complexity calculated?

This is what is meant by theta notation c(n) = Θ(n) . Note that c(n)/n² is also bounded, so c(n) = O(n²) as well — big-O notation is merely an upper bound on the complexity, so any O(n) function is also O(n²) , O(n³) ... However, since n²/c(n) = n is not bounded, then c(n) ≠ Θ(n²) .

What is Theta time complexity?

Theta Notation (Θ-notation) Since it represents the upper and the lower bound of the running time of an algorithm, it is used for analyzing the average-case complexity of an algorithm.


2 Answers

2^n is NOT big-theta (Θ) of 4^n, this is because 2^n is 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)).

Claim

2^n is not Ω(4^n)

Proof

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

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

By rearranging the inequality, we have:

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

But notice that as n → ∞, the left hand side of the inequality tends to 0, whereas the right hand side equals c > 0. Hence this inequality cannot hold for all n ≥ n0, so we have a contradiction! Therefore our assumption at the beginning must be wrong, therefore 2^n is not Ω(4^n).


Update

As mentioned by Ordous, your tutor may refer to the complexity class EXPTIME, in that frame of reference, both 2^n and 4^n are in the same class. Also note that we have 2^n = 4^(Θ(n)), which may also be what your tutor meant.

like image 85
chiwangc Avatar answered Sep 27 '22 20:09

chiwangc


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

In conclusion, the bases don't affect the complexity here; it only matters that the exponents are of the same complexity.

Edit: this answer only shows that 4^n and 2^n are of the same complexity, not that 2^n is big-Theta of 4^n: you're correct that this is not the case as 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. (Acknowledgements to @chiwangc / @Ordous for highlighting the distinction in their answer/comment.)

like image 29
Alex Riley Avatar answered Sep 27 '22 18:09

Alex Riley