# 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.
From your recursion, beacuse of $$T(n)$$ have a term $$n\log n$$ we can conclude that : $$T(n)=\Omega(n\log n)$$ and from your summation :
$$T(n)=n\log(n) \sum_{i=0}^{\log(n)}i - \sum_{i=0}^{\log(n)} i Finally $$n\log n\leq T(n)\leq n\log^2 n$$ Next step, we try to improve lower bound by induction: Suppose $$T(n)\geq c\times n\log^2 n$$ $$\rightarrow 2\times c\times\frac{n}{2}\times \log^2 \frac{n}{2}+ n\log n\geq c\times n\log^2 n$$ $$=c\times n\times \log n\times(\log n+\frac{1}{c})\geq c\times n\times \log n\times(\log n+\frac{1}{\log n})\hspace{20pt}\text{if c\leq 1 }\square$$ For sufficiently large $$n$$ (i.e. $$n\to \infty$$), and base case above inequality is correct. So we conclude that as $$n\to \infty$$ $$T(n)=\theta (n\log^2 n)$$