# If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n)))?

I guess this is true, because log is a strictly increasing function, but how do I prove it formally?

I tried something like:

Let $f(n)$ and $g(n)$ be monotonically increasing functions, $c \in \mathbb{R}$ and $n_0 \in \mathbb{N}$, such that $0 \leq f(n) \leq c g(n)$, for all $n \geq n_0$. We must find $c'$ and $n_0'$ such that $$\log(f(n)) \in \{h(n) \mid 0 \leq h(n) \leq c' \log(g(n)), \forall n \geq n_0'\}\,.$$

I got as far as $$f(n) \leq c g(n) \implies \log(f(n)) \leq \log(c g(n)) = \log(c) + \log(g(n))\,.$$

Then I got stuck.

• It is true. But not because log() is a strictly increasing function. In that case, 2^n is also a strictly increasing function but its not true for 2^n. – Severus Tux Aug 27 '17 at 0:57

You need to find a number $n'_0,c'$ such that

$$\log(c) + \log(g(n)) \le c' \log(g(n)) \text{ for all n \ge n'_0,}$$

and such that $n'_0 \ge n_0$.

So, see what you can find. Note that it's ok for $n'_0,c'$ to depend on $c$ and on $g(\cdot)$.

Hint: If you can find $n'_0,c'$ such that $\log(c) \le \log(g(n'_0))$, does anything good happen? Can you find such a $n'_0,c'$?

• Ok, how about c' = 1 + |log(c)| and n0' = n0? – matheuscscp May 20 '15 at 1:04

If we assume all functions are nonnegative and strictly increasing, then I think this relationship is true, however if we take the following cases: Let $$f(n) = 2$$ and $$g(n) = 1$$ then clearly 𝑓(𝑛)=𝑂(𝑔(𝑛)), however, 𝑙𝑔(𝑓(𝑛))=1,𝑙𝑔(𝑔(𝑛))=0, therefore, 𝑙𝑔(𝑓(𝑛))≠𝑂(𝑙𝑔(𝑔(𝑛))).