Pergunta

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.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top