1
$\begingroup$

I need to prove that if $f(n)$ tends to infinity and $f(n)=O(g(n))$ then $\log{(f(n))}=O(\log{(g(n))})$. I tried to use the fact that $g(n)/f(n) \geq 1/c$, and then it's limit is bigger than $0$, but I don't know how to continue.

$\endgroup$

1 Answer 1

2
$\begingroup$

Since $f(n)\le Cg(n)$ and $f(n)\to+\infty$ then $g(n)\ge \frac 1Cf(n)\to+\infty$ (since $C>0$).

Now use that $\ln\nearrow$ so $\ln(f(n))\le\ln(Cg(n))=\ln(C)+\ln(g(n))$

But since $\ln(g(n))\to+\infty$ for $n$ large enough it is greater than $\ln(C)$.

Therefore $\ln(f(n))\le 2\ln(g(n))$.


Your path was not wrong; you can continue like this:

$\ln(\frac{g(n)}{f(n)})\ge \ln(\frac 1C)\iff \ln(g(n))-\ln(f(n))\ge -\ln(C)\ge -\frac 12\ln(f(n))$

Similarly invoking that $\ln(C)$ is smaller than $\frac 12\ln(f(n))$ for $n$ large enough.

$\endgroup$
3
  • $\begingroup$ thank you very much first. but I don't get how you got that ln(f(n))<=2ln(g(n)) from the fact that ln(g(n))>ln(C) $\endgroup$
    – perplexed
    Commented Mar 19, 2021 at 20:26
  • $\begingroup$ Well you must be very tired, lol... $\ln(f(n))\le \ln(C)+ \ln(g(n))<\ln(g(n))+\ln(g(n))=2\ln(g(n))$ $\endgroup$
    – zwim
    Commented Mar 19, 2021 at 20:26
  • $\begingroup$ oh yes I see, thank you man! $\endgroup$
    – perplexed
    Commented Mar 19, 2021 at 20:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .