11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ran G. Apr 2 '12 at 1:10
  • $\begingroup$ @RanG. should this be closed in the light of the linked question $\endgroup$ – Suresh Apr 2 '12 at 1:13
  • $\begingroup$ @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. $\endgroup$ – Ran G. Apr 2 '12 at 1:15
  • $\begingroup$ @RanG. I tried aplying limits, but no success.. $\endgroup$ – Andre Resende Apr 2 '12 at 1:25
  • $\begingroup$ @RanG.: math.SE is already flooded with these questions, mostly tagged "algorithms". $\endgroup$ – Louis Apr 2 '12 at 11:26
14
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ In fact, for any $\epsilon >0$, $n \log^c n = O(n^{1+\epsilon})$ $\endgroup$ – Ran G. Apr 2 '12 at 1:28
  • $\begingroup$ @RanG. Yes, that is a direct consequence of the theorem. $\endgroup$ – Patrick87 Apr 2 '12 at 3:16
  • $\begingroup$ @AndreResende If my answer helped you solve your problem, and it makes sense, you can "accept" using the green check mark. It helps others see what worked for you, and might help you get more help in the future. Of course, if you'd like other answers, hold out. $\endgroup$ – Patrick87 Apr 2 '12 at 3:19
5
$\begingroup$

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.

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