# Taking the log of both sides to determine big Theta/Omega/O

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!)$?

• 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. – gmath Sep 27 '14 at 20:36
• 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 – sir_thursday Sep 27 '14 at 20:45
• 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. – gmath Sep 27 '14 at 20:47
• So $\log(f(n)) \leq c\log(g(n)) \rightarrow f(n) \in O(g(n)^c)$? – 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)$.
• 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... – sir_thursday Sep 27 '14 at 21:01