# $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?

-
As you are referring to the Wikipedia article, I refer to the notations and conventions there and assume that your $g$ should read $f$. Since $\log_b a=1$, WP talks about three cases of the master theorem. The second, $\in\Theta(n\log^k n)$, applies immediately with $k=1$. What is your question? –  Hagen von Eitzen Sep 9 '12 at 7:10
Though that is true, the only proof I have found of master theorem is though CLRS book and there, they have proved it for second case &Theta;(n<super>log<sub>b</sub>a</super>) i.e. without the log term. I want to know the way we reach to the generic form in Wikipedia from the CLRS form. –  SudanGold Sep 9 '12 at 7:22

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)$.

-
Thank you so much. Very useful. –  SudanGold Sep 9 '12 at 18:33

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.

-