Solving the recurrence relation T(n) = 2T(n/2) + nlog n via summation

Question

I have seen a few examples of using the master theorem on this to obtain O(n*log^2(n)) as an answer. I am trying to solve this by unrolling and solving the summation, but I can't seem to get the same answer. My steps are below.

Given $T(1) = 1$, $T(2) = 1$ (Time taken is constant in these two cases)

I noticed that by unrolling a few times: $$T(n) = 2\left[2T\left(\frac{n}{4}\right)+\frac{n}{2}\log{\frac{n}{2}}\right] + n\log n$$ $$T(n) = 2^{2}T\left(\frac{n}{2^{2}}\right)+n \log{\frac{n}{2}} + n\log n$$ $$T(n) = 2^{2}\left[2T(\frac{n}{8})+\frac{n}{2}\log{\frac{n}{4}}\right]+n \log{\frac{n}{2}} + n\log n$$ $$T(n) = 2^{3}T\left(\frac{n}{8}\right)+2n\log{\frac{n}{4}}+n \log{\frac{n}{2}} + n\log n$$

This looks like it follows $$T(n) = \underbrace{2^{k}T\left(\frac{n}{2^k}\right) + 2^{k}n\log\left(\frac{n}{2^{k+1}}\right)}_{\log_2n \text{ times}}$$

I use the fact that $\frac{n}{2^k} = 1$, so $k = \log_2n$. Substituting this in: $2^{k}T(\frac{n}{2^k})$ = $2^{\log_2n}T(1) = n$

Doing this summation as: $$T(n)=n + n\log_2{n}+\sum_{k=0}^{\log_2{n}-1}2^{k} n \log_2\left(\frac {n} {2^{k+1}}\right)$$ $$T(n)=n + n\log_2{n}+n\sum_{k=0}^{\log_2{n}-1}2^{k} \log_2\left(\frac {n} {2^{k+1}}\right)$$ $$T(n)=n + n\log_2{n}+n\sum_{k=0}^{\log_2{n}-1}2^{k} \log_2(n-k+1)$$

This is where I get stuck, I have a feeling I messed something up somewhere and it is making this summation much harder to solve, but I am not sure where. Where did I go wrong?

Answer 1

First, you can get the the result from the second xase of master theorem. Second, you have a mistake in your exapnsion:

$$T(n) = 2T(\frac{n}{2}) + n\log(n) = 2(2T(\frac{n}{2^2} + \frac{n}{2}\log(\frac{n}{2})) + n\log(n) = n\log(n) + n\log(\frac{n}{2}) + 2^2T(\frac{n}{2^2}) = n\log(n) + n\log(\frac{n}{2}) + 2^2(2T(\frac{n}{2^3} + \frac{n}{2^2}\log(\frac{n}{2^2})) = n\log(n) + n\log(\frac{n}{2}) + n \log(\frac{n}{2^2}) + 2^3T(\frac{n}{2^3})$$

Hence, we will have the following, if we suppose $T(1) = 0$, w.l.o.g:

$$T(n) = \sum_{i=0}^{\log(n)}n\log(\frac{n}{2^i}) = n \log(\Pi_{i=0}^{\log(n)}\frac{n}{2^i}) = n \log(\frac{n^{\log{n}}}{2^{\frac{\log(n) \times (\log(n) + 1)}{2}}}) = n \log(n) \log(\frac{n}{\sqrt{2}\sqrt{n}}) = n \log(n)\log{\frac{\sqrt{n}}{\sqrt{2}}} = \Theta(n \log^2(n))$$

Be aware that, if we change the values of $T(1)$ and $T(2)$ to the given constant values, nothing changed in the asymptotic analysis.