We saw that the solution of \(T(n) = 2T(\lfloor n/2 \rfloor) + n\) is \(O( n \lg n)\). Show that the solution of this reccurence is also \(\Omega(n \lg n)\). Conclude that the solution is \(\Theta(n \lg n)\).

In review, the text used the substitution method by guessing the solution of \(T(n) = O(n \lg n)\) and then proved that \(T(n) \leq cn \lg n\) for some constant \(c > 0\). Assume that this bound holds for all positive \(m < n\), in particular for \(m = \lfloor n/2 \rfloor\) yielding \(T(\lfloor n/2 \rfloor) \leq c \lfloor n/2 \rfloor \lg \lfloor n/2 \rfloor)\). Substituting into the recurrence yields

\[\begin{split} T(n) & \leq 2(c \lfloor n/2 \rfloor \lg \lfloor n/2 \rfloor) + n \\ & \leq cn \lg (n/2) + n \\ & = cn \lg n - cn \lg 2 + n \\ & = cn \lg n - cn + n \\ & \leq cn \lg n \\ \end{split}\]

where the last step holds for \(c \geq 1\).

Next, we guess the solution of \(T(n) = \Omega(n \lg n)\) and then prove that \(T(n) \geq cn \lg n\) for some constant \(c > 0\). Assume that this bound holds for all positive \(m < n\), in particular for \(m = \lfloor n/2 \rfloor\) yielding \(T(\lfloor n/2 \rfloor) \geq c \lfloor n/2 \rfloor \lg \lfloor n/2 \rfloor)\). Substituting into the recurrence yields

\[\begin{split} T(n) & \geq 2(c \lfloor n/2 \rfloor \lg \lfloor n/2 \rfloor) + n \\ & \geq cn \lg (n/2) + n \\ & = cn \lg n - cn \lg 2 + n \\ & = cn \lg n - cn + n \\ & \geq cn \lg n \\ \end{split}\]

where the last step holds for \(c \leq 1\).

Combining these together, we have that \(c_1 n \lg n \leq T(n) \leq c_2 n \lg n\) where \(c_1 \leq 1\) and \(c_2 \geq 1\) which implies that \(T(n) = \Theta(n \lg n)\).