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

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

• Controversial opinion: it's bad notation since there are multiple valid interpretation and nobody agrees on which to use. Don't use it. – Raphael Sep 4 '19 at 17:25

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