What is the runtime complexity for this recurrence relation $T\left(n\right)\ =\ 2T\left(\frac{n}{2}\right)\ +\ n\ lg\ n$?

Question

I am using the master theorem

case 1:

is $f\left(n\right)\ =\ n\ lg\ n\ ∈\ O\left(n^{\log_b\left(a\right)-ε}\right)\ ∈\ O\left(n^{\log_2\left(2\right)-ε}\right)\ ∈\ O\left(n^{1-ε}\right)$?

for some ε > 0?

Since ε > 0, then $f\left(n\right)\ =\ n\ lg\ n\ \ ∉\ O\left(n^{1-ε}\right)$

Hence, the first form of the Master theorem cannot be used.

case 2:

Is $f\left(n\right)\ =\ n\ lg\ n\ ∈\ Θ\left(n^{\log_b\left(a\right)}\right)\ ∈\ Θ\left(n^{\log_2\left(2\right)}\right)\ ∈\ Θ\left(n^1\right)$?

Since $f\left(n\right)\ =\ n\ lg\ n\ \ ∉\ Θ\left(n\right)$ , the second form of the Master theorem cannot be used.

case 3:

Is $f\left(n\right)\ =\ n\ lg\ n\ ∈\ Ω\left(n^{\log_b\left(a\right)+ε}\right)\ ∈\ Ω\left(n^{\log_2\left(2\right)+ε}\right)\ ∈\ Ω\left(n^{1+ε}\right)$

Since $f\left(n\right)\ =\ n\ lg\ n\ \ ∉\ Ω\left(n^{1+ε}\right)$, the third form of the Master theorem cannot be used.

master theorem is not working, how do I get the runtime complexity of this recursion?

Answer 1

For simplicity take n to be a power of 2, ie $n=2^k$, and we can also take log to be base 2. Then by iterating the same step:

$T(n)=2T(\frac{n}{2})+n\log(n)=4T(\frac{n}{4})+n\log(\frac{n}{2})+n\log(n)=nT(1)+n\log(\frac{n}{2^{k-1}})+n\log(\frac{n}{2^{k-2}})+...+n\log(\frac{n}{2})+n\log(n)$

Put $n=2^{k}$, to get $T(n)=2^{k}T(1)+2^{k}(1+2+...+k)=2^{k}T(1)+2^{k}\frac{(k)(k+1)}{2}$

Now use that $k=\log(n)$ to conclude that $T(n)=\Theta(n\log(n)^2)$