## Exercise 4.3-3

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