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

Let us assume $T(n) \ge c (n + b) \lg (n + b)$ for all $n \ge n_0$, where $b$, $c$, and $n_0$ are positive constants.

The last step holds as long as $(n - cn - dc) \ge 0 \implies n \ge cd / (1 - c)$. For example, $d = 0$, $n \ge 1$, and $% $.