4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)$ $\endgroup$ – Yiğit Aras Tunalı Oct 27 at 12:50
  • $\begingroup$ Thanks, there was a small typo. $\endgroup$ – Yuval Filmus Oct 27 at 12:51
  • $\begingroup$ 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 ? $\endgroup$ – Yiğit Aras Tunalı Oct 27 at 12:55
  • $\begingroup$ You tell me why. $\endgroup$ – Yuval Filmus Oct 27 at 12:56
  • $\begingroup$ I'll look into a bit more and try to do that then. $\endgroup$ – Yiğit Aras Tunalı Oct 27 at 12:57
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ FYI, Yuval Filmus had already mentioned this counterexample in his answer. $\endgroup$ – ruakh Oct 27 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.