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?

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

1 Answer 1


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.
  • 2
    $\begingroup$ I miss a proof that we can always choose $c$ such that $c\cdot t(n) \le 2^{c\cdot t(n)}$. $\endgroup$
    – G. Bach
    Commented Nov 17, 2013 at 1:20
  • $\begingroup$ Yes, I agree with you. I was thinking of that $t(n)$ as being a coefficient. Oops. I'll look over it again tomorrow. $\endgroup$ Commented Nov 17, 2013 at 3:16
  • 1
    $\begingroup$ 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) $\endgroup$ Commented Nov 17, 2013 at 4:02
  • $\begingroup$ Could you leave another hint? I'm not so sure how $t(n)$ can be expressed as a power of $2$. $\endgroup$ Commented Nov 17, 2013 at 7:41
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Nov 18, 2013 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.