Error in the CLRS book for analyzing time complexity?

Question

4.3-8 Using the master method in Section 4.5, you can show that the solution to the recurrence $T(n) = 4T(n/2) + n^2$ is $\Theta(n^2)$.

Wouldn't it be $\Theta(n^2 \log n)$?

Answer 1

You are right, this is the second case of the Master Theorem (in its generic form) with $c=\log_b a = \log_2 4 =2$ and $k=0$. Indeed, we have $$ T(n) = aT\left(\frac{n}{b}\right) + f(n) $$ where $a=4$, $b=2$, and $f(n)=n^2$. Setting $k=0$, since $f(n) \in \Theta(n^c\log^k n) = \Theta(n^2)$, we get $T(n) = \Theta(n^c\log^{k+1} n) = \Theta(n^2\log n)$.