$T(n) = 2T(n/2) + n \log n$ recurrence relation using master theorem Assume that 
$$T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n \log n)$$
By Generic form of master theorem with $a = 2$,  $b = 2$ and $f(n) = c \, n \log n$, it can easily be proved that $T(n) = \Theta(n \log^2 n)$.
Though I am not able to understand how exactly does this derive from the master thoerem. Is there any way we can prove the generic form using the original form?
 A: This was already answered multiple times on the site but here we go. Let $S(k)=2^{-k}T(2^k)$, then $S(k)=S(k-1)+\Theta(k)$, hence $S(k-1)+Ak\leqslant S(k)\leqslant S(k-1)+Bk$ for some finite $A$ and $B$. Iterating this yields $S(0)+A\sum\limits_{i=1}^ki\leqslant S(k)\leqslant S(0)+B\sum\limits_{i=1}^ki$, hence $S(k)=\Theta(k^2)$. 
The final step, which cannot be made rigorous without some further hypothesis (such as, that the sequence $(T(k))_k$ would be nondecreasing), is to assert that $T(2^k)=\Theta(2^kk^2)$ implies that $T(n)=\Theta(n(\log n)^2)$.
A: Here you can consider $S(n)=T(n)/cn$ for which 
$S(n) = S(n/2) + \log (n)$
$k$ iterations of this give
$S(n) = S(n/{2^k}) + k \log 2 (\log_2 n - \frac{(k-1)}{2})$
Taking $k = \log_2 n + O(1)$ and performing some algebra, the answer is:
$T(n) = (\frac{c \log 2}{2}) n \log_2^2 n + O(n\log n)$  .
The "master theorem" does not pin down the coefficient of the main term, it was attained here by explicit calculation and choosing $k$ as large as possible.
