4.3-2

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)$. I am not going to prove for O. I will prove for $\Omega$ let $T(n) \geq c n lg n$ $$ T(n) = 2 c n/2 lg(n/2)+n $$ $$ T(n) = n c lg(n/2)+n $$ $$ T(n) = n c lg(n) - nc +n $$ $$ T(n) = n c lg(n) - ( - nc +n ) $$ if above eq has to be greater than n lg n the residual (in brackets) should be $\leq 0$ $$ - nc +n \leq 0 $$ $$ - nc \leq -n $$ $$ c \leq 1 $$ base case: $$ T(2) = \theta(2) \leq c 2 lg 2 $$ $$ T(2) = \theta(2) \leq c 2 $$ for sufficiently large c above equation is true.