1
$\begingroup$

I am working on an asymptotic analysis question from a data structures past paper, and I need to show that $$\lim\limits_{n\to\infty}\frac{n}{(\log n)^2}=\infty$$

Could I have a hint for working out how to show this, please?

$\endgroup$
3
$\begingroup$

Hint: Use L'hopital's rule on the limit since it's in an indeterminate form.

$\endgroup$
3
  • $\begingroup$ I have tried to use your hint, but am struggling to make progress. Let $f(n) = n$ and $g(n) = (\log n)^2$ (where we are working base 2). Note that $g(n) = (\frac{\ln(n)}{\ln(2)})^2$. Then $\lim_{n\to\infty}\frac{f(n)}{g(n)} = \lim_{n\to\infty}\frac{f'(n)}{g'(n)} = \lim_{n\to\infty}\frac{1}{2\ln(n)\cdot (\ln2)^{-2}} = 0 \not= \infty.$ Have I done something wrong? $\endgroup$ – Caleb Owusu-Yianoma May 16 '15 at 18:00
  • $\begingroup$ You should have $g'(n) = \frac{2\ln(n)}{n(\ln(2))^2}$. $$((\ln(n))^2)' =2(\ln(n))(\ln(n))' = \frac{2\ln(n)}{n}$$ $\endgroup$ – user222031 May 16 '15 at 18:31
  • $\begingroup$ Of course. You correctly identified my mistake. I have solved the problem now. :) $\endgroup$ – Caleb Owusu-Yianoma May 16 '15 at 18:53
2
$\begingroup$

note that $ log(n) \leq n^\alpha $ for any $\alpha >0$ for instance chose $\alpha = 1/4$ now apply comparison test

Alter: Use L'Hospitals Rule

$\endgroup$
5
  • $\begingroup$ How can I show that $\log n \leq n^\alpha \space \forall \alpha \gt 0$? $\endgroup$ – Caleb Owusu-Yianoma May 16 '15 at 16:55
  • $\begingroup$ @CKKOY Do you know $n \geq \log(n)$. $\endgroup$ – user222031 May 16 '15 at 16:57
  • $\begingroup$ @user222031: Yes, I do know that fact. :) $\endgroup$ – Caleb Owusu-Yianoma May 16 '15 at 17:01
  • $\begingroup$ math.stackexchange.com/questions/65202/how-to-prove-log-n-n $\endgroup$ – user229886 May 16 '15 at 17:02
  • 1
    $\begingroup$ @CKKOY refer above mentioned post $\endgroup$ – user229886 May 16 '15 at 17:02
2
$\begingroup$

Hint: $$\frac{\sqrt n}{\log n}\to +\infty \implies \frac{n}{(\log n)^2} \to +\infty$$ And you can have many ways to prove the first part.

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