Solving $T(n)= 2T(n/2)+n \lg (n)$ I am trying to solve a recursive function: 
$$ T(n)= 2 T(n/2)+n \lg(n), \quad n>2,\quad T(2)=2,\quad n = 2^{k}$$
Master theorem didn't work. The result is pointless (if I did it right).
Any suggestions? 
 A: I prefer to resort to ad-hoc tricks for solving such recursions. Divide by $n$ to get:
$$
\frac{T(n)}{n} = \frac{T(n/2)}{(n/2)} + \lg n.
$$
Assuming $n$ is a power of $2$, it is easy to see that
$$
\begin{eqnarray*}
\frac{T(n)}{n} 
&=&
\lg (n) + \lg \left( \frac{n}{2} \right) + \lg \left( \frac{n}{2^2} \right) + \cdots + \lg (1)
\\ &=&
\lg n + (\lg n - 1) + (\lg n -2) + \cdots + 0
\\ &=&
\frac{1}{2} \lg n \cdot (\lg n +1)
\\ &=&
\Theta((\lg n)^2),
\end{eqnarray*}
$$
which implies $T(n) = \Theta(n (\lg n)^2)$. 
It is conventional to hand-wave at this point and mumble something about $n$ not a power of $2$... 
A: The recurrence only seems to be well defined when $n$ is a power of $2$, so let $n=2^k$. Then we can expand the recurrence until we reach T(2):
$$\begin{align}T(2^k) &= 2^kk + 2\cdot 2^{k-1}(k-1) + 2^2\cdot2^{k-2}(k-2) + \cdots + 2^{k-2}\cdot 2^2 2 + 2^{k-1}2 \\
&= 2^k \sum _{j=1}^{k} j = 2^k\frac{k(k+1)}{2} = 2^{k-1}k(k+1)\quad \mathrel{\Big[=} O(n\log^2(n))\Big]\end{align}$$
A: While one case of the master theorem easily applies, this one is also simple enough that it can be solved via induction.  Consider $$\begin{align*}T(2^k) &= k2^k + 2T(2^{k-1})\\
&= k2^k+2\bigl((k-1)2^{k-1}+2T(2^{k-2})\bigr) \\
&= k2^k+(k-1)2^k+4T(2^{k-2})
\end{align*}$$ etc; you should be able to continue this to find the value of $T(2^k)$, and then use that to prove that the asymptotic result holds for values of $n$ that aren't powers of $2$.
