4
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.