Exact meaning of $2^{\mathcal{O}(f(n))}$

Question

In Sipser's Introduction to the Theory of Computation he uses the notation $2^{\mathcal{O}(f(n))}$ to denote some asymptotic running time.

For example he says that the running time of a single-tape deterministic turing machine simulating a multi-tape non-deterministic turing machine is

$\mathcal{O}(t(n)b^{t(n)})=2^{\mathcal{O}(t(n))}$ where $b$ is the maximal number of options in the transtition function.

I was wondering if someone can clarify the exact definition of this for me:

My assumption is that if $g(n)=2^{\mathcal{O}(f(n))}$ then there exists $N \in \mathbb{Z}$ and $c \in \mathbb{R}$ s.t.

$g(n) \leq 2^{cf(n)}=(2^{f(n)})^c$ for all $n>N$.

Thank you

Answer 1

The class $O(f(n))$ consists of all functions $\phi$ such that for some $N,c > 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))$.