Is asymptotic ordering preserved when taking log of both functions?

Question

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.

Answer 1

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))$.

Answer 2

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.