Where The Log Vanishes

A candidate solves $T(n) = 4T(n/2) + n \lg n$ by saying: "master theorem case 2, so $T(n) = \Theta(n^{\log_2 4} \lg n) = \Theta(n^2 \lg n)$ ."

Compare $f(n) = n \lg n$ against $n^{\log_b a} = n^2$ and give the correct answer.

$\Theta(n \lg^2 n)$

$\Theta(n^2)$ . $n \lg n$ is polynomially smaller than $n^2$ , so the leaves dominate and the $\lg n$ never reaches the answer.

$\Theta(n^2 \lg n)$ . Case 2 applies whenever $f(n)$ carries a log factor.

$\Theta(n^2 \lg^2 n)$ , since the tree has $\lg n$ levels and each contributes a log.