Meaning of a big O in an exponent

Question

What does this expression f(n) = 2^O(n) mean, in an exact formal manner?

Answer 1

The statement f(n) = 2^O(n) is equivalent to

log_2(f(n)) = O(n)

(actually, any logarithm will do), so it means that there is some constant C > 0 such that

log_2(f(n)) <= C*n  <=> f(n) <= 2^(C*n)

for all large enough n. Now, a^b*c = (a^b)^c, so another way to put it is to say

f(n) = O(b^n)

for some b > 0. This b could be 1.5, or 4, or 1000000000000, so it doesn't tell you too much. All it gives you is that f is exponential, so it's asymptotically better than O(n!), but it doesn't tell you whether it's pretty bad, bad, really bad or truly catastrophically bad.