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$$.