why is $O(t(n)b^{t(n)}) = 2^{O(t(n))}$
I think I solved my problem...

Just as a simple numerical example: $2^6 = 2^{2\cdot3} = (2^{2})^3 = (2^{3})^2$

So if we have $2^{ct(n)}$ for some positive integer $c$ (as in the definition of O-notation) then we can choose a different base s.t. it is a power of two to the $t(n)$ power:
\begin{equation}
  2^{ct(n)} = (2^{c})^{t(n)}
\end{equation}

Then clearly, we can choose $c$ s.t. $2^c \geq b$. Hence:
\begin{equation}
  b^{t(n)} \leq (2^c)^{t(n)}
\end{equation}

Now multiplying the LHS by $t(n)$ does not matter because I can still easily choose $c$ s.t:
\begin{equation}
  t(n)b^{t(n)}  \leq (2^c)^{t(n)}
\end{equation}

Finally, we see that: \begin{equation}
ct(n)b^{t(n)}  \leq (2^c)^{t(n)}
\end{equation}

because we can still easily choose $c$.

EDIT I made a mistake with thinking of the $t(n)$ term in front of $b^{t(n)}$ as a coefficient... Anyway, here is a revised solution:

\begin{align*}
O(t(n)b^{t(n)}) =&amp; 2^{O(t(n))} \\
ct(n)b^{t(n)} =&amp; 2^{ct(n)} \\
ct(n)b^{t(n)} =&amp; (2^c)^{t(n)} \\
2^{\log_2(ct(n))}b^{t(n)} =&amp; (2^c)^{t(n)}
\end{align*}
Now suppose $b=2$. Then we can see that the term $2^{\log_2(ct(n))}$ is dominated by $2^{t(n)}$. i.e.
\begin{equation}
  2^{\log_2(ct(n))}2^{t(n)} = 2^{\log_2(ct(n)) + t(n)} = 2^{O(t(n))}
\end{equation}
Now, for $b\geq 2$ we know the $2^{\log_2(ct(n))}$ is negligible and so we are left with:
\begin{align*}
 O(b^{t(n)}) =&amp; 2^{O(t(n))} \\
 cb^{t(n)} =&amp; (2^c)^{t(n)}
\end{align*}
I think these two are asymptotically equivalent in the sense that $b$ is fixed and then we can choose some $c$ to satisfy the above, but what happens to the $\leq$ in the definition of $O$-notation?


Is this revision correct?
How does one read the original expression intuitively? Usually if you have $f(n) = O(g(n))$, we can think that $f$ is "bounded by" or "at most" $g$. In this scenario we have another $O$-notation as an exponent.