Solving the recurrence $T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{2}\log(n)$ Please help me solve the recurrence
$$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{2}\log(n) $$
 A: Here is an exact solution of a related recurrence that has the same complexity as yours. We take $T(0)=0$ and the recurrence is
$$T(n) = 2 T(\lfloor n/2 \rfloor) + \frac{1}{2} n \; (\lfloor\log_2 n\rfloor+1).$$
Let the binary digits of $n$ be given by
$$n = \sum_{k=0}^{\lfloor\log_2 n\rfloor} d_k 2^k.$$
Then the exact solution to the recurrence is
$$T(n) = \frac{1}{2}\sum_{k=0}^{\lfloor\log_2 n\rfloor} 2^k
(\lfloor\log_2 n\rfloor +1 - k)\sum_{j=k}^{\lfloor\log_2 n\rfloor} d_j 2^{j-k}.$$
Now an upper bound on $T(n)$ is given by the case where we have a string of ones, producing
$$T(n) \le \frac{1}{2}\sum_{k=0}^{\lfloor\log_2 n\rfloor} 2^k
(\lfloor\log_2 n\rfloor +1 - k)\sum_{j=k}^{\lfloor\log_2 n\rfloor} 2^{j-k}
\\= \frac{1}{2}\times
\left(\lfloor\log_2 n\rfloor^2 2^{\lfloor\log_2 n\rfloor}
+ 3 \lfloor\log_2 n\rfloor 2^{\lfloor\log_2 n\rfloor}
- 2 \times 2^{\lfloor\log_2 n\rfloor} + \lfloor\log_2 n\rfloor +3\right).$$
We get a lower bound when $n$ is a one digit followed by zeros, giving
$$T(n)\ge \frac{1}{2}\sum_{k=0}^{\lfloor\log_2 n\rfloor} 2^k
(\lfloor\log_2 n\rfloor +1 - k) 2^{\lfloor\log_2 n\rfloor-k}
= \frac{1}{2}\times 2^{\lfloor\log_2 n\rfloor} \sum_{k=0}^{\lfloor\log_2 n\rfloor}
(\lfloor\log_2 n\rfloor +1 - k)
\\ = \frac{1}{2}\times 2^{\lfloor\log_2 n\rfloor}
\left(\frac{1}{2} \lfloor\log_2 n\rfloor^2
+\frac{3}{2} \lfloor\log_2 n\rfloor +1\right).$$
Taking the two dominant terms from the upper and lower bound we get the asymptotic complexity as
$$\Theta\left( \lfloor\log_2 n\rfloor^2 2^{\lfloor\log_2 n\rfloor}\right)
= \Theta(\log^2 n\times n).$$
This link points to a series of similar calculations.
A: You can use the master theorem:
Using the master theorem's notation, we have $a = 2$; $b = 2$; $c = \log_b{a} = 1$; $f(n) = \frac{n}{2}\log(n)$.
This corresponds to the master theorem's case 2, where: $f(n) = \Theta\left( n^{c} \log^{k} n \right)$, which implies $T(n) = \Theta\left( n^{c} \log^{k+1} n \right)$.
Replacing with our values, we get:
$T(n) = \Theta\left( n^1 \log^{1+1} n \right) = \Theta\left( n \log^{2} n \right)$
