Problem Detail: $T(n)=2T(n/2) + nlog^2(n)$. If I try to substitute $m = log(n)$ I end up with $T(2^m)=2 T(2^{m-1}) + 2^mlog^{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(nlog^3 n)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6833
