Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

$T(n)=2T(n/2) + n\log^2(n)$.

If I try to substitute $m = \log(n)$ I end up with

$T(2^m)=2 T(2^{m-1}) + 2^m\log^{2}(2^m)$.

Which isn't helpful to me. Any clues?

PS. hope this isn't too localized. I specified that the problem was a squared logarithm which should make it possible to find for others wondering about the same thing.

share|improve this question
    
It seems very "second case of master theorem"-y to me. –  The Unfun Cat Nov 22 '12 at 9:28
1  
Also note $\log^2 (2^m) = m^2$. This method does work. –  Peter Shor Nov 22 '12 at 12:00
add comment

1 Answer

up vote 5 down vote accepted

This is indeed the second case in the Master Theorem. For the standard recursion form $$T(n)=a\;T(n/b)+f(n),$$ you get $a=b=2$, and therefore $f(n)=\Theta(n^{\log_b a} \log^2 n)=\Theta(n \log^2 n)$.

Applying the Master theorem yields $T(n)=\Theta(n\log^3 n)$.

share|improve this answer
2  
Note that some sources have a more restricted second case. –  Raphael Nov 22 '12 at 10:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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