Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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
add comment

2 Answers 2

up vote 0 down vote accepted

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

share|improve this answer
Thank you so much. Very useful. –  SudanGold Sep 9 '12 at 18:33
add comment

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.