1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – weee Oct 30 '18 at 11:15
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.