# Time Complexity OF NTM vs TM

In Sipser, It is given Pg. 284

Let t(n) be a function, where t(n) ≥ n. Then every t(n) time non-deterministic single-tape Turing machine has an equivalent 2 O(t(n)) time deterministic single tape Turing machine

In the given proof, at end they conclude

O(t(n)bt(n)) = 2O(t(n)).

where b is the maximum number of legal choices given by N’stransition function

I am unable to understand how did they conclude so>

• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Apr 16 '17 at 19:11
• Be aware of what "$2^{O(\dots)}$" means -- it's horrible abuse of notation. – Raphael Apr 16 '17 at 19:11

You can write, if $b\gt 1$, $$b^{t(n)}=2^{\log_2{b}\times t(n)}=2^{O(t(n))}$$
So, $$O(t(n)b^{t(n)})=O(t(n)2^{O(t(n))})=O(2^{\log_2{t(n)}}2^{O(t(n))})=2^{O(t(n))}$$
To elaborate, $$O(x2^{O(x)})=O(2^{\log x}2^{O(x)})=O(2^{O(x)+\log x})=O(2^{O(x)})$$ which means it is eventually upper bounded by some $$c2^{O(x)}=2^{\log cO(x)}=2^{O(x)}$$
Note that if $b=1$, then the non deterministic Turing machine is effectively a deterministic Turing machine, so you can still write it as $O(t(n))$, which is as expected.
• @user2984602 $O(x2^{O(x)})=O(2^{\log x}2^{O(x)})=O(2^{O(x)+\log x})=O(2^{O(x)})$, which means it is eventually upper bounded by some $c2^{O(x)}=2^{\log cO(x)}=2^{O(x)}$. Does this clarify your question? – GoodDeeds Apr 16 '17 at 18:36