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 &gt; 0$, $a &gt; 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.
Do what you did, but let $a = (3^{0.2})$... that should do it, right?

The reason that what you did didn't work is as follows. The big-oh bound is not tight; while the logarithm to the fifth is indeed big-oh of linear functions, it is also big oh of the fifth root function. You need this stronger result (which you can also get from the theorem) to do what you're doing.