0

I think it's not true. I disprove it by assuming $f(n) = 1$, $g(n) = 2$.

so $$\lim \frac{\log\left(f(n)\right)}{\log\Big(g\big(g(n)\big)\Big)} = 0$$

but $$\lim \frac{f(n)}{g(n)} = 0.5$$

which disprove it, nevertheless, I am not sure if $\log(1) =O(0)$ have any meaning.

thanks

F.A.
  • 1,001
GlobalCitezen
  • 1
  • At a first sight I thought it was uncorrect since $\log g(n)\not \to 0$ but it is correct by the definition. Note that it should be $\log(1) =o(\log 2)$. – user Mar 28 '18 at 14:28

1 Answers1

0

For the definition take a look here prove that $\log f(n) = o(\log g(n))$ implies $f(n)=o(g(n))$.

Your choice seems indeed a bit strange since $\log g(n)\not \to 0$ but it is correct by the definition $\log( f(n) )=0=o(\log(g(n)))$.

As an alternative let consider

  • $f(n)=e^{\frac 1 {n^2}}$
  • $g(n)=e^{\frac 1 {n}}$
user
  • 154,566
  • Is e ^(1/n^2) =o e ^(1/n)? I think I can't use it as an counter example since those functions are not "growing" as n ---> infinite (excuse me for not using proper mathematics terms) nevertheless, I anyway can't see why f(n) =o g(n) with those values. Can you try get it into my intuition please? – GlobalCitezen Mar 29 '18 at 10:53
  • @GlobalCitezen Note that $\log f(n) = 1/n^2$ and $\log g(n)=1/n$ then $\frac{\log f(n)}{\log g(n)}=\frac1n \to 0$ but $\frac{f(n)}{g(n)}=e^{\frac1{n^2}-\frac1n}\to 1$ – user Mar 29 '18 at 11:19