# f(n) tends to infinity and $f(n)=O(g(n))$ then $\log{(f(n))}=O(\log{(g(n))})$

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.

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.

• 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) Commented Mar 19, 2021 at 20:26
• 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))$
– zwim
Commented Mar 19, 2021 at 20:26
• oh yes I see, thank you man! Commented Mar 19, 2021 at 20:35