1
$\begingroup$

I'm having trouble with little o notation.

Help me show that:

$2(n^2 + 100n)\log^5n = o(n^2\sqrt{n})$.

It is the last hwk on my sheet and I don't understand it, if someone can help me with little o notation, that would be great thank you kindly.

$\endgroup$
  • $\begingroup$ Have you been given a definition of the little-oh notation? $\endgroup$ – Gerry Myerson Oct 8 '12 at 22:53
  • $\begingroup$ Can you show that $\lim_{n \to \infty} \frac{n}{\log n}= \infty$? $\endgroup$ – Alex Oct 9 '12 at 2:03
1
$\begingroup$

Hint: For positive functions $f(n)$ and $g(n)$, to show that $f(n)=o(g(n))$, one needs to show that $$\lim_{n\to\infty} \frac{f(n)}{g(n)}=0.$$ In our particular case, after writing down what $\dfrac{f(n)}{g(n)}$ is, I would suggest dividing top and bottom by $n^2$. You will get something like $$2\left(1+\frac{100}{n}\right) \frac{\log^5n}{n^{1/2}}.$$ Finally, you need information on the speed of growth of the logarithm, and powers of it, in comparison with the speed of growth of positive powers of $n$. It might help to note that $$\frac{\log^5 n}{n^{1/2}}=\left(\frac{\log n}{n^{1/10}}\right)^5.$$

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