Master's theorem

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

• 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. Sep 17, 2018 at 7:01
• Unregistered users cannot see the contents of the website. Could you please quote relevant part here? Sep 17, 2018 at 8:57

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