Solving the recurrence $T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{2}\log(n)$

Solution 1:

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.