# Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem

Solving $$T(n) = 2T(\frac{n}{2}) + n\log(n)$$ without master theorem, given $$T(1) = 1$$

My approach with recurrence tree:

$$n \sim n\log(n)$$

$$\frac{n}{2} \sim 2 \frac{n}{2}\log(\frac{n}{2})$$

$$\frac{n}{4} \sim 4 \frac{n}{4}\log(\frac{n}{4})$$

Hence the summation must follow as:

$$T(n) = \sum_{i=0}^{\log(n)} n\log(\frac{n}{2^i})$$ $$= \sum_{i=0}^{\log(n)} n(\log(n) - i)$$ $$=(n\log(n) \sum_{i=0}^{\log(n)}i) - (\sum_{i=0}^{\log(n)} i)$$

I can not go further from here, any help is welcome.

For direct result let's use direct summation assuming $$n=2^k$$: $$T(n) = 2T\left(\frac{n}{2}\right) + n\log(n)=2\left[ 2T\left(\frac{n}{2^2}\right) +\frac{n}{2}\log \frac{n}{2}\right]+ n\log(n) = \\ =2^2T\left(\frac{n}{2^2}\right)+n\log \frac{n}{2}+ n\log(n) =\\ =\cdots=\\ =2^kT\left(1\right)+n\log \frac{n}{2^{k-1}}+ \cdots +n\log \frac{n}{2}+n\log(n)=\\ =2^kT\left(1\right) +n\log 2 + \cdots +n\log 2^k=\\ =nT\left(1\right) +n\log 2 (1 + \cdots + k) =nT\left(1\right) + \frac{k(k+1)}{2} n\log 2 \in \Theta (n \log^2 n)$$ where, of course, $$k=\log_2 n$$. Hope you can obtain from here everything what you wanted.
At end let me note also, that $$n \sim n\log(n)$$ and other equivalences, which you are using, are not correct, if we understand standard $$\lim \frac{f}{g}=1$$, for symbol "$$\sim$$". Correct is, for example, $$n = o(n\log(n))$$ etc.