Определенно, если у вас есть O(2^n), было бы лучше. Потому что можно надеяться, что в худшем случае это будет плохо. Но этот худший случай может случиться редко. Следовательно, средняя сложность времени может быть намного лучше. Например, у вас есть ситуация, которая возникает с вероятностью 1/2^n, и алгоритм для этого случая работает с 2^n затратами на вычисления, но стоимость алгоритма для всех остальных случаев составляет 1. Следовательно, сложность этого алгоритма составляет O(2^n), но средняя сложность составляет O(1).
Однако, как и в приведенном выше примере, это не может произойти для алгоритма с \Theta(2^n).
Но в Theta(2^n) вы будете уверены, что средняя сложность времени составляет 2^n, и это может быть ужасно.