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.
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
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.
