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

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?

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.

• So? Let's leave a bit of work to the questioner... I added a step to make it clearer. Still one has to reason why denominator is unbounded. – weee Oct 30 '18 at 11:15

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.$$

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.