0
$\begingroup$

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?

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

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.
$\endgroup$
  • 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 Nov 17 '13 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$ – CodeKingPlusPlus Nov 17 '13 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$ – Luke Mathieson Nov 17 '13 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$ – CodeKingPlusPlus Nov 17 '13 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$ – Luke Mathieson Nov 18 '13 at 3:39

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.