4.3-5

Show that $\theta(n lg n)$ is the solution to the “exact” recurrence (4.3) for merge sort.
equation 4.3 $$ T(n) = T(\lfloor (n/2) \rfloor)+ T(\lceil (n/2) \rceil)+ \theta(n) $$ Let $ T(n) \leq c n lg n $ $$ T(n) = c n/2 lg (n/2) + c n/2 lg(n/2) + n $$ $$ T(n) = c n lg (n/2) + n $$ $$ T(n) = c n lg (n/2) + n $$ $$ T(n) = c n lg n - c n + n $$ $$ T(n) = c n lg n -( c n - n )$$ the residual should be greater than zero $$cn - n \geq 0 $$ $$c \geq 1 $$ if we want prove the base case we can do T(2) and T(3) else we can add $c_2 n $ at the end of our assumption and prove for T(1)