I am stuck trying to understand a proof in my book for why, given a nondeterministic single-tape Turing machine $N$ that runs in time $t(n) \geq n$, the deterministic single-tape Turing machine $D$ that simulates it will run in time $2^{O(t(n))}$.

I do understand the idea of the proof: $D$ simulates $N$ by doing a breadth-first search of $N$'s computation history tree starting from the root node. Every node of the tree has $b$ possible branches given by $N$'s transition function, and any branch of $N$ has length at most $t(n)$. So the running time of $D$ is $O(t(n)b^{t(n)})$ because it has to go at most down $b^{t(n)}$ branches that have a maximum length of $t(n)$ each.

So far so good. Then the book just says $O(t(n)b^{t(n)}) = 2^{O(t(n))}$ with no further explanation, and this concludes the proof. Where does this equation come from? Where does the $2$ come from? Thank you!


1 Answer 1


For any fixed $b$, we have $b < 2^k$ for some $k$ large enough, and $t(n) < 2^{t(n)}$ for $n$ large enough. So for $k,n$ large enough we have $$ t(n) b^{t(n)} \le 2^{t(n)} \left(2^k\right)^{t(n)} = 2^{t(n) + kt(n)} = 2^{O(t(n))}. $$

  • $\begingroup$ What is the advantage of putting this result in the form $2^{O(t(n))}$? It seems less intuitive in this case. $\endgroup$
    – Elena
    Commented Dec 16, 2019 at 12:52
  • $\begingroup$ @Elena That I do not know, I am sorry. My guess is, the context in the book may be more helpful, what does the author do with the result? $\endgroup$
    – gt6989b
    Commented Dec 16, 2019 at 17:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .