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 recurrence is also \(\Omega(n \lg n)\). Conclude that the solution is \(\Theta(n \lg n)\).
To show \(T(n) = \Omega(n \lg n)\), we need to show \(T(n) \ge c n \lg n\), for all \(n \ge n_0\), where \(c\) and \(n_0\) are some positive constants.
Let’s assume, \(T(n) \ge c n \lg n\), and it holds for all positive \(m < n\), in particular for \(m = \lfloor n/2 \rfloor\).
\[\begin {aligned} T(n) &= 2T(\lfloor n/2 \rfloor) + n \\ &\ge 2 c \lfloor n/2 \rfloor \lg \lfloor n/2 \rfloor + n \\ &\ge 2 c (n/2 - 1) \lg (n/2 - 1) + n \\ &= 2 c \left(\frac {n - 2} 2\right) \lg \left(\frac {n - 2} 2\right) + n \\ &= c(n - 2) \lg (n - 2) - c(n - 2) \lg 2 + n \\ &= c(n - 2) \lg (n - 2) + (1 - c)n + 2c \\ \end {aligned}\]As in previous exercise, this is inconclusive, and we need to compensate for the \(-2\) term. We’ll do that by modifying our previous guess, by adding 2 our initial guess.
Let’s assume, \(T(n) \ge c (n + 2) \lg (n + 2)\)
\[\begin {aligned} T(n) &\ge 2 c (\lfloor n/2 \rfloor + 2) \lg (\lfloor n/2 \rfloor + 2) + n \\ &\ge 2 c (n/2 - 1 + 2) \lg (n/2 - 1 + 2) + n \\ &= 2 c \left(\frac {n + 2} 2\right) \lg \left(\frac {n + 2} 2\right) + n \\ &= c(n + 2) \lg (n + 2) - c(n + 2) \lg 2 + n \\ &= c(n + 2) \lg (n + 2) + \textcolor {blue} {(1 - c)n - 2c} \\ &\ge c(n + 2) \lg (n + 2) \\ \end {aligned}\]The last step holds as long as the term marked in blue is positive, i.e. \(n \ge \frac {2c}{1 - c}\).
Hence, we need \(0 \le c < 1\).
If we pick \(c = 0\), then our assumption holds for \(n \ge 0 = n_0\).
If we pick \(c = 1/2\), then our assumption holds for \(n \ge 2 = n_0\).