# What is the case 2 in master theorem?

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:

1. 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?

• Nothing. Some sources go with a weaker case 2. – Raphael Apr 11 '15 at 14:43