# How to prove that $n(\log_3(n))^5 = O(n^{1.2})$?

This a homework question from Udi Manber's book. Any hint would be nice :)

I must show that:

$n(\log_3(n))^5 = O(n^{1.2})$

I tried using Theorem 3.1 of book:

$f(n)^c = O(a^{f(n)})$ (for $c > 0$, $a > 1$)

Substituing:

$(\log_3(n))^5 = O(3^{\log_3(n)}) = O(n)$

but $n(\log_3(n))^5 = O(n\cdot n) = O(n^2) \ne O(n^{1.2})$

Thank you for any help.

• What methods can you use? take a look at this answer it might give you some ideas. Also here there is plenty of useful information. – Ran G. Apr 2 '12 at 1:10
• @RanG. should this be closed in the light of the linked question – Suresh Apr 2 '12 at 1:13
• @Suresh I'm not sure. I fear if we don't we would be flooded with such questions (which maybe should fit Mathematics better). But it is a valid question. – Ran G. Apr 2 '12 at 1:15
• @RanG. I tried aplying limits, but no success.. – Andre Resende Apr 2 '12 at 1:25
• @RanG.: math.SE is already flooded with these questions, mostly tagged "algorithms". – Louis Apr 2 '12 at 11:26

Do what you did, but let $a = (3^{0.2})$... that should do it, right?
• In fact, for any $\epsilon >0$, $n \log^c n = O(n^{1+\epsilon})$ – Ran G. Apr 2 '12 at 1:28
Another way to think about it more intuitively, is to see that the main thing you have to show is that $(\log_3(n))^5$ is $O(n^{0.2})$, or equivalently that $\log_3(n)$ is $O(n^{0.04})$. Logs always grow slower than any constant power of n, no matter how small.
If you want to formalize the last sentence, then you can use theorem 3 with a sufficiently small $\alpha$ as @RanG mentions in the comment on @Patrick87's answer.