How can we compare the time complexity of O(2^n) and Θ(2^n)?

Question

I have to compare the time complexity of O(2^n) and Θ(2^n) for a homework problem .

I believe that Θ(2^n) is better since it covers the upper and the lower bound of 2^n but I'm not sure.Thank you for your time .

Answer 1

Definitely, if you have O(2^n) would be better. Because you can have hope that just in the worst case scenario it would be bad. But that worst case might happen rarely. Hence, the average time complexity could be much better. For example, you have a situation that takes happen with the probability of 1/2^n and the algorithm runs for this case with 2^n computation cost, but the cost of the algorithm for all other cases is 1. Hence, the complexity of this algorithm is O(2^n), but the average complexity is O(1).

However likes the above example, cannot happen for an algorithm with \Theta(2^n). But in Theta(2^n) you will be sure the average time complexity is 2^n and it could be awful.