What is the meaning of $g(n) = 2^{O(f(n))}$?

Question

Given functions f and g, as above, what exactly does it mean? Does it mean, for example, that g(n) is exactly equal to $2^{h(n)}$ for some function h contained in $O(f(n))$ - or does it rather mean that $g(n) = O(2^{h(n)})$ for some function h contained in $O(f(n))$? Any help would be much appreciated!

Answer 1

Remember big-Oh $(O)$ is an asymptotically tight bound. So if for some $f,g$ you have $f(x) = O(g(x)$, then as $x$ approaches infinity, $f$ is almost a constant multiple times $g$. This tells us that there exists a natural number $N$ and a point $x_0$ such that,

$$ |f(x)| \leq N\cdot g(x), \tag{$x \geq x_0$}$$

This can be used to show that all elements in $O(g(x))$ are constant multiples of each other and can be considered "equivalent". So you can say,

$$ 2^{O(f(n))} \equiv 2^{h(n)} \tag{ $h(n) \in O((f(n))$}$$ This is not the same as $O(2^{f(n)})$ as then for any $g(n)$ in this set, there is a natural number $N'$ and point $n_0$ such that,

$$ |2^{f(n)}| \leq N' \cdot g(n) \tag{$n \geq n_0$}$$

but this is not the same as $2^{|f(n)|}$ which is what the first equation would be when raising both sides as a power of 2.

Answer 2

It means that for all large enough $N$, there exists $C>0$ such that $$g(n)\le 2^{Cf(n)}.$$ Alternatively, it means that $$\log g(n)=O(f(n)).$$