[Solved]: What is the case 2 in master theorem?

Problem Detail: 

I am confused about the statement of the Master theorem in CLRS book.

Here is the link of the book CLRS.

In page 94, the theorem, in case 2, states that:

2. If $\displaystyle f(n)=\Theta(n^{\log_ba})$, then $T(n) = \Theta(n^{\log_ba}\lg n)$.

What if $T(n) = T(n/2) + \Theta(\lg n)$? We have $f(n)=\Theta(\lg n)\neq\Theta(1)$.

I found the slides of the CLRS book in MIT website here where the statement of the theorem looks different in case 2 (page 5).

If $\displaystyle f(n)=\Theta(n^{\log_ba}\lg^k n)$, then $T(n) = \Theta(n^{\log_ba}\lg^{k+1} n)$.

What am I missing here?

Asked By : Kira

Answered By : Yuval Filmus

There are several different versions of the Master Theorem. This situation is common in mathematics: a well-known theorem may have several common versions, for example the Chernoff–Hoeffding bound(s). Perhaps one version is the original, and another is a widely known strengthening; or perhaps one version is the original, and another is the one appearing in textbooks, which is slightly weaker (since the proof of the complete theorem is too long or too difficult). Sometimes an apparently weaker version of the theorem is equivalent to the full theorem with a short proof (for example, Hilbert's Nullstellensatz).

As Raphael mentions in his comment, here you are encountering two common versions of the Master Theorem, one of which is stronger and can handle your case. If you were writing a paper, I would recommend citing a source which states (and preferably proves) the version of the theorem you use.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41250

3.2K people like this

 Download Related Notes/Documents