How to give a good guess to the recurrence relation problem I have been trying to solve the following recurrence relation
$$T(n)=2T(\frac{n}{2}) + nlgn$$
by using substitution method.
I started to compute $T(1)$ ,$T(4)$,$T(8)$,$T(16)$ to guess a solution as below:
$$T(1)=1$$
$$T(2)=2+2lg2=4$$
$$T(4)=8+8lg2=16$$
$$T(8)=32+24lg2=56$$
$$T(16)=112+64lg2=176$$
My guess is that $T(n)$ should be something like $nlg^2n$ but I couldn't get a correct term.
Can anyone improve my guess?
 A: At each step, we replace $n$ with $n/2$ and multiply the equation by $2$:
\begin{align*}
T(n) - 2T(\tfrac{n}{2}) &= n\lg n \\
2T(\tfrac{n}{2}) - 2^2T(\tfrac{n}{2^2}) &= n\lg \tfrac{n}{2} \\
2^2T(\tfrac{n}{2^2}) - 2^3T(\tfrac{n}{2^3}) &= n\lg \tfrac{n}{2^2} \\
2^3T(\tfrac{n}{2^3}) - 2^4T(\tfrac{n}{2^4}) &= n\lg \tfrac{n}{2^3} \\
&~~\vdots \\
2^{\lg n - 1}T(2) - 2^{\lg n}T(1) &= n\lg2 \\
\end{align*}
Summing the $\lg n$ equations together, we note that the LHS telescopes, yielding:
\begin{align*}
T(n) - 2^{\lg n}T(1) &= n\sum_{k=0}^{\lg n - 1} \lg \tfrac{n}{2^k} \\
T(n) - n \cdot 1 &= n\sum_{k=0}^{\lg n - 1} (\lg n - k) \\
T(n) - n &= n\sum_{k=0}^{\lg n - 1}\lg n - n\sum_{k=0}^{\lg n - 1} k \\
T(n) - n &= n(\lg n)(\lg n) - n\frac{(\lg n)(\lg n - 1)}{2} \\
T(n) &= \frac{1}{2}n\lg^2 n + \frac{1}{2}n \lg n + n
\end{align*}
Thus, we conclude that $T(n) = \Theta(n \lg^2 n)$, which you suspected.
A: Take $n = 2^kp$ where $p$ is odd, then 
$$T(2^{k+1}p) = 2T(2^kp) + 2^{k}p\log(2^kp) $$
So $$\dfrac{T(2^{k+1}p)}{2^{k+1}} = \dfrac{T(2^kp)}{2^k} + \dfrac{pk\log(2)+p\log p }{2}$$
Then we have
$$\dfrac{T(2^{k+1}p)}{2^{k+1}} = T(p) + \dfrac{p\log2}{2}(\sum_{j=0}^k j) + \frac{p(k+1)\log p}{2}$$
$$T(2^{k+1}p) = 2^{k+1}T(p) + 2^k p \log2\dfrac{(k+1)k}{2} + p(k+1)(\log p)2^k$$
If you plug $p=1$, this can be simplified a bit
A: There  is another  closely  related recurrence  that  admits an  exact
solution. Suppose we have $T(0)=0$ and $T(1)=1$ and for $n\ge 2$
$$T(n) = 2 T(\lfloor n/2 \rfloor) + n \lfloor \log_2 n \rfloor.$$
Furthermore let the base two representation of $n$ be
$$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$
Then  we can  unroll the  recurrence to  obtain the  following exact
formula for $n\ge 2$
$$T(n) = 2^{\lfloor \log_2 n \rfloor}
+ \sum_{j=0}^{\lfloor \log_2 n \rfloor -1} 
2^j \times (\lfloor \log_2 n \rfloor - j) \times 
\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}
\\ = 2^{\lfloor \log_2 n \rfloor}
+ \sum_{j=0}^{\lfloor \log_2 n \rfloor -1} 
(\lfloor \log_2 n \rfloor - j) \times 
\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$
Note that this formula produces matching values for the data at $n=2^j$ 
posted by the OP in the question, namely the sequence
$$1, 4, 16, 56, 176, 512, 1408, 3712\ldots$$
Now to get an upper bound consider a string of one digits to obtain
$$T(n) \le 2^{\lfloor \log_2 n \rfloor}
+ \sum_{j=0}^{\lfloor \log_2 n \rfloor -1} 
(\lfloor \log_2 n \rfloor - j) \times 
\sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k.$$
This simplifies to
$$\lfloor \log_2 n \rfloor^2 2^{\lfloor \log_2 n \rfloor}
+ \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor}
- 2^{\lfloor \log_2 n \rfloor}
+ \lfloor \log_2 n \rfloor + 2.$$
This bound is actually attained and cannot be improved upon, just like
the lower bound,  which occurs with a one digit  followed by zeroes to
give
$$T(n) \ge
2^{\lfloor \log_2 n \rfloor}
+ \sum_{j=0}^{\lfloor \log_2 n \rfloor -1} 
(\lfloor \log_2 n \rfloor - j) \times 2^{\lfloor \log_2 n \rfloor}.$$
This simplifies to
$$\frac{1}{2} \lfloor \log_2 n \rfloor^2 2^{\lfloor \log_2 n \rfloor}
+ \frac{1}{2} \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor}
+ 2^{\lfloor \log_2 n \rfloor}.$$
Joining the dominant terms of the upper and the lower bound we obtain
the asymptotics
$$\lfloor \log_2 n \rfloor^2 \times
2^{\lfloor \log_2 n \rfloor}
\in \Theta\left((\log_2 n)^2 \times 2^{\log_2 n}\right) 
= \Theta\left((\log n)^2 \times n\right).$$
The above would  seem to be in agreement with  what the Master theorem
would produce.

There are some additional calculations using this method at this
MSE link.
A: In
$T(n)=2T(\frac{n}{2}) + n\ lgn$
put
$n=2^m$.
This becomes
$T(2^m)
=2T(2^{m-1})+m 2^m
$.
(Note:
I fixed an error
so the following
has been completely rewritten.)
Let
$S(m) 
=T(2^m)
$.
Then
$S(m)
=2S(m-1)+m2^m
$.
Dividing by $2^m$,
$2^{-m}S(m)
=2^{-m-1}S(m-1)+m
$.
Letting
$U(m)
=2^{-m}S(m)
$,
$U(m) 
=U(m-1)+m
$
or
$U(m)-U(m-1)
=m
$.
Summing,
$U(m)
=m(m-1)/2
\approx m^2/2
$.
Working back,
$S(m)
=2^mU(m)
\approx 2^mm^2/2
$.
Finally,
$T(n)
=S(lg\ n)
\approx n (lg\ n)^2/2
$.
A: with Mathematica we get this here
$\left\{\left\{a(n)\to 2 c_1 n-n \log \left(n^{\frac{1}{2} \left(-\frac{\log
   (n)}{\log (2)}-1\right)}\right)\right\}\right\}$
