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

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!

• Commented Feb 13, 2023 at 22:10
• It is likely there is a duplicate here as well. I haven't searched on this site, though. Commented Feb 13, 2023 at 22:13

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.

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)).$$