1
$\begingroup$

Is Master's theorem applicable on $T(n) = 2 T(\frac{n}{2})+n\log n$ ?

I got this doubt from here:

https://gateoverflow.in/227814/introduction-to-algorithms

$\endgroup$
2
  • 2
    $\begingroup$ Wikipedia has a good description of the master theorem: en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms). I suggest ignoring all other online sources. $\endgroup$ Sep 17, 2018 at 7:01
  • 1
    $\begingroup$ Unregistered users cannot see the contents of the website. Could you please quote relevant part here? $\endgroup$
    – xskxzr
    Sep 17, 2018 at 8:57

1 Answer 1

1
$\begingroup$

Yes, Master's theorem is applicable to equations of type:

$$T(n) = aT(\frac{n}{b}) + \Theta(n^k log^pn)$$

where $a \geq 1$, $b \gt 1$, $k \geq 0$ and for some real number p.

This is slightly modified and we can apply it more easily. The results are as follows:

  1. if $a \gt b^k$, then $$T(n) = \Theta(n^{log_ba})$$

  2. if $a = b^k$, then

    a) if $p > -1$, $$T(n) = \Theta(n^{log_ba} log^{p+1}n)$$

    b) if $p = -1$, $$T(n) = \Theta(n^{log_ba} loglogn)$$

    c) if $p < -1$, $$T(n) = \Theta(n^{log_ba})$$

  3. if $a < b^k$, then

    a) if $p \geq 0$, $$T(n) = \Theta(n^klog^pn)$$

    b) if $p < 0$, $$T(n) = O(n^k)$$

$\endgroup$
2

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.