1
$\begingroup$

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?

  • 0
    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 Θ(nlogba) i.e. without the log term. I want to know the way we reach to the generic form in Wikipedia from the CLRS form.2012-09-09

2 Answers 2

2

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

  • 0
    Thank you so much. Very useful.2012-09-09
0

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.