Big Oh-Complexity of $\log(\frac{n}{\log(n)})$ vs $\frac{\sqrt{n}}{\log(\sqrt{n})}$

Question

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?

Answer 1

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.

Answer 2

We obtain \begin{align*} \color{blue}{f(n)}&=\log\left(\frac{n}{\log n}\right)\\ &=\log n-\log\log n\\ &=\log n+O(\log n)\\ &=O(\log n)\\ &=O\left(\frac{\sqrt{n}}{\log n}\right)\tag{$(\log n)^2=O(\sqrt{n})$}\\ &=O\left(\frac{\sqrt{n}}{\frac{1}{2}\log n}\right)\\ &\,\,\color{blue}{=O(g(n))} \end{align*}

in accordance with OP's assumption.

Answer 3

Informally, log's don't count for much, so $f(n)\approx \log(n)$ and $g(n)\approx \sqrt{n}$, so $f(n)/g(n)\rightarrow 0$.

Formally, for $n\geq3$ $$ \frac{f(n)}{g(n)} = \frac{\log\left(\frac{n}{\log{n}}\right)}{\frac{\sqrt{n}}{\log(\sqrt{n})}} $$ $$ < \frac{\log(n)}{\frac{\sqrt{n}}{\log(\sqrt{n})}}= \frac{\log(n) \log(\sqrt{n})}{\sqrt{n}} $$ $$ = \frac12 \frac{\log(n)^2 }{\sqrt{n}}. $$

Now using L'Hôpital's rule twice, $$ \lim_{n\rightarrow\infty} \frac{f(n)}{g(n)}\leq \lim_{n\rightarrow\infty}\frac{\log(n)^2 }{\sqrt{n}} = \lim_{n\rightarrow\infty} \frac{2 \log(n)/n}{1/(\,2\sqrt{n}\,)} $$ $$ = \lim_{n\rightarrow\infty} \frac{4 \log(n)}{\sqrt{n}} = \lim_{n\rightarrow\infty} \frac{4/n}{1/(\,2\sqrt{n}\,)} = \lim_{n\rightarrow\infty} \frac{8}{\sqrt{n}}=0. $$