# why is $O(t(n)b^{t(n)}) = 2^{O(t(n))}$

I have a question about simplifying O-notation. Specifically, why is $O(t(n)b^{t(n)}) = 2^{O(t(n))}$ where $t(n)$ is the running time of an algorithm?

• Are you clear about what $2^{O(\dots)}$ is supposed to mean? (Start e.g. here.) – Raphael Nov 18 '13 at 21:03

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)}) =& 2^{O(t(n))} \\ ct(n)b^{t(n)} =& 2^{ct(n)} \\ ct(n)b^{t(n)} =& (2^c)^{t(n)} \\ 2^{\log_2(ct(n))}b^{t(n)} =& (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)}) =& 2^{O(t(n))} \\ cb^{t(n)} =& (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?

1. Is this revision correct?
2. 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.
• I miss a proof that we can always choose $c$ such that $c\cdot t(n) \le 2^{c\cdot t(n)}$. – G. Bach Nov 17 '13 at 1:20
• Yes, I agree with you. I was thinking of that $t(n)$ as being a coefficient. Oops. I'll look over it again tomorrow. – CodeKingPlusPlus Nov 17 '13 at 3:16
• You might want to deal with the multiplicative $t(n)$ (kind-of) separately: can you express $t(n)$ as power of two? (It's not so different from what you've already shown) – Luke Mathieson Nov 17 '13 at 4:02
• Could you leave another hint? I'm not so sure how $t(n)$ can be expressed as a power of $2$. – CodeKingPlusPlus Nov 17 '13 at 7:41
• @CodeKingPlusPlus there's a way you can rewrite any expression to be $2^{something}$. A simple one might be if you have a number $x$, then there's some $y$ such that $x = 2^{y}$, even better, there's a way, if you "know" $x$, to get $y$ - you can do the same thing with a function etc. – Luke Mathieson Nov 18 '13 at 3:39