# Is asymptotic ordering preserved when taking log of both functions?

In one of my exercise sheets I have the following question;

Let $$f,g\colon \mathbb{N}\longrightarrow\mathbb{R}$$ be positive functions with $$f(n) \in O(g(n))$$. Prove or disprove; $$\ln(f(n)) \in O(\ln(g(n))$$.

I first thought this would be the case since $$\ln$$ is a monotonically increasing function (derivative is positive), and so the asymptotic ordering of these functions wouldn't be affected. But then there was an example stuck in my mind and which I have later on seen on the internet as well.

Let $$f(n) = 2^n,g(n)=3^n$$. Since $$f(n) \in O(g(n))$$ given $$\lim_{n\to \infty} \frac{3^n}{2^n}=\infty$$. Then $$\ln(f(n))=n\ln 2$$ and $$\ln(g(n))=n\ln 3$$ which leads to $$0< \lim_{n\to \infty} \frac{n\ln 3}{n\ln 2} < \infty$$ which implies $$\ln (f(n)) \in \Theta(\ln(g(n)))$$. The growth rates have changed, yes, but since $$\Theta(f) = O(f) \cap\Omega(f)$$ isn't, technically speaking, $$\ln(f(n)) \in O(\ln(g(n)))$$? I am a bit confused as going by my own steps the initial assumption seems right but I am not entirely convinced for either possibility. Because if this is correct I feel like I can extend the same idea for exponentiation as well maybe.

Anything to prove or disprove the statement with an explanation would be really welcome as I am a bit lost at the moment.

If $$f(n) = \Theta(g(n))$$, then in particular $$f(n) = O(g(n))$$. This is just like saying that if $$x = y$$, then in particular $$x \leq y$$.

Suppose that $$f(n) = O(g(n))$$. According to the definition, there are $$N,c$$ such that all $$n \geq N$$ satisfy $$f(n) \leq cg(n)$$. Taking logarithms, this implies that $$\log f(n) \leq \log c + \log g(n)$$. Does this imply the existence of a constant $$c'$$ such that for large enough $$n$$, $$\log f(n) \leq c' \log g(n)$$?

Here is a simple counterexample: $$f(n) = e$$ and $$g(n) = 1$$. Clearly $$f(n) = O(g(n))$$, but $$\log f(n) = 1$$ whereas $$\log g(n) = 0$$. However, in this case $$\log g(n)$$ is not positive, so you may want to rule that case out. However, we can correct this example so that $$\log g(n)$$ is strictly positive, by taking $$g(n) = 1 + 1/n$$. In this case $$\log g(n) = 1/n$$ which is strictly positive, yet still $$\log f(n)$$ is not $$O(\log g(n))$$.

Here is a sufficient condition for the deduction to work. Suppose that there exists $$N'$$ and $$C > 1$$ such that for all $$n \geq N'$$, it holds that $$g(n) > C$$. Then for $$n \geq \max(N,N')$$, we have $$\log f(n) \leq \log c + \log g(n) \leq \left( \frac{\log c}{\log C} + 1 \right) \log g(n),$$ and so $$\log f(n) = O(\log g(n))$$.

• Thank you for your answer! I understand the reasoning but I am not able to make the final step to as how did you arrive to $\left( \frac{\log c}{C} + 1 \right) \log g(n)$ – Yiğit Aras Tunalı Oct 27 '19 at 12:50
• Thanks, there was a small typo. – Yuval Filmus Oct 27 '19 at 12:51
• Oh, I see but still that last part kinda bugs me as I can't totally wrap my head around it. Especially that last part you corrected now. It is just $\frac{\log c * \log(g(n))}{\log C} + \log g(n)$ why use such a construct ? – Yiğit Aras Tunalı Oct 27 '19 at 12:55
• You tell me why. – Yuval Filmus Oct 27 '19 at 12:56
• I'll look into a bit more and try to do that then. – Yiğit Aras Tunalı Oct 27 '19 at 12:57

A simple counter example is f (n) = 2, g (n) = 1 + 1/n.

f(n) is only twice as large as g(n), but log(f(n)) becomes arbitrarily large compared to log (g(n)) because log (g(n)) becomes very small.

• FYI, Yuval Filmus had already mentioned this counterexample in his answer. – ruakh Oct 27 '19 at 17:31