Problem Detail: 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(ncdot n) = O(n^2) ne O(n^{1.2})$ Thank you for any help.
Asked By : Andre Resende
Answered By : Patrick87
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/974
