1
$\begingroup$

I'm not sure how to get from the left hand side to the right. It appears in Sipser's Introduction to the Theory of Computing, in a proof of showing that a $t(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{O(t(n))}$ time deterministic single-tape Turing machine.

$\endgroup$
4
$\begingroup$

Note that for every number $x$ it holds that $x=2^{\log x}$. Using this, we can do the following:

$t(n)b^{t(n)}=2^{\log t(n)}b^{t(n)}=2^{\log t(n)}({2^{\log b}})^{t(n)}=2^{\log t(n)}2^{t(n)\log b}=2^{\log t(n)+t(n)\log b}$. Now, assuming $t$ is non-decreasing, we have that $\log t(n)=O(t(n))$, so ${\log t(n)+t(n)\log b}=O(t(n))$, and we're done.

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