# single tape NTM to single tape DTM equivalence

I am having some trouble understanding the equivalence of DTM's and NTM's. If you have Sipser its under 7.11; where he says that any NTM $N$ that halts after $t(n)$ steps has an equivalent DTM $D$ that halts after $2^{O(t(n))}$ steps.

He says that $N$ 's "computation tree" has at most $b^{t(n)}$ leaves, where $b$ is the maximum number of choices a transition can have in $N$, and the tree is at most $t(n)$ "levels deep", since $N$ halts after $t(n)$ steps per definition.

Now if one would like to simulate $N$ with $D$ you would have to go through no more than $t(n)b^{t(n)}$ steps to halt.

Then Sipser says that $O(t(n)b^{t(n)})= 2^{O(t(n))}$ which I dont understand.

In my understanding the runtime of $D$ should be $O(b^{t(n)})$ where $b >0$.

Can someone clear this up for me ?

Relevant pages in Sipser are 255-256.

The claim is that for constant $b$, if $f = O(t(n) b^{t(n)})$ then $f = 2^{O(t(n))}$. Indeed, $xb^x \leq b(b+1)^x$, and so $$Ct(n) b^{t(n)} \leq Cb (1+b)^{t(n)} = 2^{\log_2(1+b) \cdot t(n) + \log_2 b + \log_2 C}.$$ From here it's not hard to check that $f = O(t(n)b^{t(n)})$ implies $f = 2^{O(t(n))}$.
• $Ct(n)$ ... until $2^{+\log_2 C}$, until then it is trivial, I dont understand how both sides are equal. – zython Jun 18 '17 at 14:30