Chapter 5.1: A First Recurrence: The Mergesort Algorithm

Mergesort sorts a given list of numbers by first dividing them into two equal halves, sorting each half separately by recursion, and then combining the results of these recursive calls - using the linear time algorithm for merging sorted lists that we saw in chapter 2.

Two approaches to solving recurrences are as follows:

• “Unrolling” the recursion, accounting for the running time across the first few levels, and identifying a pattern that can be continued as the recursion expands. One then sums the running times over all levels of the recursion and thereby arrives at a total running time.
• A second way is to start with a guess for the solution, substitute it into the recurrence relation, and check that it works. Formally, one justifies this plugging-in using an argument by induction on n. There is a useful variant of this method in which one has a general form for the solution, but does not have exact values for all the parameters. By leaving these parameters unspecified in the substitution, one can often work them out as needed.

This chapter was hard to find important points - perhaps because I haven't seen this explained in class. 7/10.