Show that $\Theta(n \lg n)$ is the solution to the “exact” recurrence (4.3) for merge sort.

To show $\Theta$ bound, separately show $O$ and $\Omega$ bounds.

For $O$-bound: Assume $T(n) \le c (n - b) \lg (n - b)$ for some positive constant $b$. For $\Omega$-bound: Assume $T(n) \le c (n + b) \lg (n + b)$ for some positive constant $b$.

And then proceed as in the previous exercises.