I've managed to confuse myself over this detail:

Obviously: $n^2 \notin \Theta(n)$

Now if we take the $\log$ of both sides, we get:

$$\log(n^2) \leq \log(cn)$$

$$2\log(n) \leq \log(c) + \log(n)$$

Suddenly this equation looks true... that you can find a $c$ to satisfy the $\Theta$ definition. Obviously, I know this is not the case. Question is, when can you take the log of both sides to prove a O/Omega/Theta definition? What about for $2^n \in \Theta(n!)$?

  • 2
    $\begingroup$ Of course, what you have discovered is that $f_n = O(g_n)$ and $\log (f_n) = O(\log g_n)$ are not equivalent. For $O,\Theta$ etc notations you have to be very very careful and check its validity in every step. Also coming back to your question: $\log f_n = O(\log g_n)$ implies $f_n$ is $O(g_n^c)$ for some constant $c$ which is hidden inside the $O$ notation. $\endgroup$ – gmath Sep 27 '14 at 20:36
  • $\begingroup$ How can $\log(f(n)) \in O(\log(g(n)) \rightarrow f(n) \in O(g(cn))$? It's false that $\log(n^2) \in O(\log(n)) \rightarrow n^2 \in O(cn)$ Thanks for helping $\endgroup$ – sir_thursday Sep 27 '14 at 20:45
  • $\begingroup$ What I meant was $\log f(n) = O(\log g(n))$ implies $f(n) = O((g(n))^c)$ for some $c$ hidden in the previous $O$-notation. $\endgroup$ – gmath Sep 27 '14 at 20:47
  • $\begingroup$ So $\log(f(n)) \leq c\log(g(n)) \rightarrow f(n) \in O(g(n)^c)$? $\endgroup$ – sir_thursday Sep 27 '14 at 20:51

As gmath shows, you can never take the logarithm of both sides in view of proving asymptotic estimates. More explicitly, you cannot deduce (say) $f = O(g)$ from $\log f = O(\log g)$. Stated differently, if $f = O(g)$ then it doesn't follow that $e^f = O(e^g)$. Even more simply, it is not the case that $e^{O(f)} = O(e^f)$. The root cause of this is the failure of $e^{O(x)} = O(e^x)$.

Which transformations are we allowed to use? If $\phi(O(x)) = O(\phi(x))$ then we can deduce $f = O(g)$ from $\phi^{-1}(f) = O(\phi^{-1}(g))$, since $$f = \phi(\phi^{-1}(f)) = \phi(O(\phi^{-1}(g))) = \phi(\phi^{-1}(O(g))) = O(g).$$ As an example, $\log(O(x)) = O(\log x)$, and so we can deduce $f = O(g)$ from $e^f = O(e^g)$.

| cite | improve this answer | |
  • $\begingroup$ Oh okay, so when showing that $2^{n^2} \notin O(2^n)$ through contradiction, we can't do something like: $2^{n^2} \leq c \times 2^n$ and take the log of both sides to get $n^2 \leq \log(c) + n$ and so forth... $\endgroup$ – sir_thursday Sep 27 '14 at 21:01

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.