Exact meaning of $2^{\mathcal{O}(f(n))}$
The class $O(f(n))$ consists of all functions $\phi$ such that for some $N,c &gt; 0$, we have $\phi(n) \leq Cf(n)$ for all $n \geq N$.

The class $2^{O(f(n))}$ is simply
$$
2^{O(f(n))} = \{ 2^{\phi(n)} : \phi(n) = O(f(n)) \},
$$
which is essentially what you wrote.



A different way of looking at this is that $O(f(n))$ stands for some function $\phi(n)$ such that $\phi(n) \leq Cf(n)$ for all large enough $n$.

Given this point of view, $2^{O(f(n))}$ simply stands for some function of the form $2^{\phi(n)}$, where $\phi(n) = O(f(n))$.