2
$\begingroup$

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

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

1 Answer 1

4
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ Note that some sources have a more restricted second case. $\endgroup$
    – Raphael
    Nov 22, 2012 at 10:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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