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

This exact recurrence is:

\[T(n) = \begin{cases} \Theta(1) & \text{if $n = 1$,} \\ T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n) & \text{if $n > 1$.} \\ \end{cases}\]

We start with showing this recurrence is \(O(n \lg n)\). We guess that \(T(n) \leq c(n-b) \lg (n-b)\). Substituting this into the recurrence yields

\[\begin{split} T(n) & \leq c (\lceil n/2 \rceil - b) \lg (\lceil n/2 \rceil - b) + c (\lfloor n/2 \rfloor - b) \lg (\lfloor n/2 \rfloor - b) + dn \\ & \leq c(n/2 + 1 - b) \lg (n/2 + 1 -b) + c(n/2 - b) \lg (n/2 - b) + dn \\ & = c\left( \frac{n - b}{2} \right) \lg \left(\frac{n - b}{2} \right) + c\left( \frac{n - b}{2} \right) \lg \left(\frac{n - b}{2} \right) + dn \\ & = c(n - b) \lg \left(\frac{n - b}{2} \right) + dn \\ & = c(n - b) \lg (n - b) - c(n - b) + dn \\ & = c(n - b) \lg (n - b) - cn + bc + dn \\ & \leq c(n-b) \lg (n-b) \\ \end{split}\]

Where the last step \(c(n - b) \lg (n - b) - cn + bc + dn \leq c(n-b) \lg (n-b)\) holds for any \(c > d\).

Next we will show that this recurrence is \(\Omega(n \lg n)\). We guess that \(T(n) \geq c(n+b) \lg (n+b)\). Substituting this into th erecurrence yields

\[\begin{split} T(n) & \geq c (\lceil n/2 \rceil + b) \lg (\lceil n/2 \rceil + b) + c (\lfloor n/2 \rfloor + b) \lg (\lfloor n/2 \rfloor + b) + dn \\ & \geq c(n/2 + b) \lg (n/2 + b) + c(n/2 - 1 + b) \lg (n/2 - 1 + b) + dn \\ & = c\left( \frac{n + b}{2} \right) \lg \left(\frac{n + b}{2} \right) + c\left( \frac{n + b}{2} \right) \lg \left(\frac{n + b}{2} \right) + dn \\ & = c(n + b) \lg \left(\frac{n + b}{2} \right) + dn \\ & = c(n + b) \lg (n + b) - c(n + b) + dn \\ & = c(n + b) \lg (n + b) - cn - bc + dn \\ & \geq c(n+b) \lg (n+b) \\ \end{split}\]

Where the last step \(c(n + b) \lg (n + b) - cn - bc + dn \geq c(n+b) \lg (n+b)\) holds for any \(c < d\).

Our recurrence being in \(O(n \lg n)\) and \(\Omega(n \lg n)\) implies that it is in \(\Theta(n \lg n)\).