Section 5.1 The Mergesort Algorithm

The mergesort algorithm with which we are all familiar provides an excellent opportunity to study recurrence relations. As with many divide-and-conquer algorithms, the behvior of mergesort can be described with a template such as: divide the input into two equally-sized pieces, recursively solve those pieces and then recombine the results into an overall solution. For mergesort, as with many algorithms of this nature, it will “bottom out” at a base case of constant size.

The recurrence relation for mergesort is T(n) ⇐ 2T(n/2) + cn since it takes constant time to divide the input up into two pieces of size n/2 and then T(n/2) time solving each piece before they are combined back together, again in linear time. This type of analysis can be completed by a method known as “unrolling” the recursion.

Unrolling the recursion of a problem involves a few steps. The first consists of analysing the first few levels to determine how much time each of these levels will take. Eventually, a pattern will make itself evident to the careful observer and so the next step is observing that pattern and formalizing it. Finally, the algorithm analyst must sum the running time for each level of recursion to find the total running time of the algorithm.

There are also methods using substitution and partial substitution to solve for the running time but these seem to me to be unhelpful unless you already have a solid guess for the running time. Even in the case that you have a solid guess for running time though, it is still a guess and more likely to lead you down the wrong path than unrolling the recursion, so why not just unroll it from the start in order to save yourself time, frustration and guesswork? These two substitution sections at the end are my main issue with the section 5.1 since they seem to add now value, at least in my mind. Maybe I simply don't understand them though.