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.

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

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ In fact, for any $\epsilon >0$, $n \log^c n = O(n^{1+\epsilon})$ $\endgroup$
    – Ran G.
    Apr 2, 2012 at 1:28
  • $\begingroup$ @RanG. Yes, that is a direct consequence of the theorem. $\endgroup$
    – Patrick87
    Apr 2, 2012 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, 2012 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.