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?
$\begingroup$
$\endgroup$
1
asked Nov 17, 2013 at 0:19
-
1$\begingroup$ Are you clear about what $2^{O(\dots)}$ is supposed to mean? (Start e.g. here.) $\endgroup$– RaphaelCommented Nov 18, 2013 at 21:03
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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?
- 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.
answered Nov 17, 2013 at 0:44
-
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. BachCommented 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