Оператор f(n) = 2^O(n) эквивалентен
log_2(f(n)) = O(n)
(фактически, любой логарифм подойдет), так что это означает, что существует некоторая константа C > 0 такая, что
log_2(f(n)) <= C*n <=> f(n) <= 2^(C*n)
для всего достаточно большого n.Теперь a b * c = (a b ) c , так что еще один способ выразить это, скажем,
f(n) = O(b^n)
длянекоторые b > 0.Это b может быть 1.5, или 4, или 1000000000000, так что это не говорит вам слишком много.Все, что он дает вам, это то, что f экспоненциально, поэтому он асимптотически лучше, чем O(n!), но он не говорит вам, довольно ли это плохо, плохо, действительно плохо или действительно катастрофически плохо.