[Solved]: Solving recurrence with logarithm squared $T(n)=2T(n/2) + n \log^2n$

Problem Detail: 

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

Asked By : The Unfun Cat

Answered By : A.Schulz

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6833