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

Question

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.

Answer 1

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.

Answer 2

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.