Could you help me see which of the two functions
$f(n) = \log(\frac{n}{\log(n)})$ and $g(n) = \frac{\sqrt{n}}{\log(\sqrt{n})}$
grows asymptotically faster? I would say that $f(n) = \mathcal{O}(g(n))$, since $f(n)$ is logarithmic, but I am struggling to prove that formally. Could you help me with that?
Best Answer
If you are not interested in the asymptotic expansion per se you could just take the quotient and use L'Hôpital's rule:
$$\lim_{x\to\infty}\frac{f(x)}{g(x)}=\lim_{x\to\infty}\frac{f'(x)}{g'(x)}=\lim_{x\to\infty}\frac{\frac{1}{x}-\frac{1}{x\log x}}{\frac{1}{\sqrt x\log x}-\frac{2}{\sqrt x\log^2 x}}=\lim_{x\to\infty}\frac{1-\frac{1}{\log x}}{\frac{\sqrt x}{\log x}-\frac{2\sqrt x}{\log^2 x}}=0.$$ Thus, $g$ grows faster.