# Solving recurrence with logarithm squared $T(n)=2T(n/2) + n \log^2n$

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

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

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