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.

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.

StackExchange Computer Science Q#974, answer score: 14