Show that is the solution to the “exact” recurrence (4.3) for merge sort.

To show bound, separately show and bounds.

For -bound: Assume for some positive constant . For -bound: Assume for some positive constant .

And then proceed as in the previous exercises.

If you have any question or suggestion or you have found any error in this solution, please leave a comment below.