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.

This section explores a more general version of recurrence problem than the previous one did. This type of recurrence creates recursive calls on q subproblems of size n/2. Mergesort uses q = 2, but can in fact be 1 or >2. Generalizing the inequality from the previous section gives us: T(n) ⇐ qT(n/2) + cn when n > 2.

For algorithms that split the input into more than 2 subproblems we can still use the same unrolling technique discussed in the previous section. Consider a problem where q = 3. The first level will have 1 problem of size n, which will be split into 3 problems of size n/2, which is then split into 9 problems of size n/4 and so on. This makes it obvious that work is increasing throughout the running of the problem. To identify the pattern, we can notice that the number of problems per level is simply our q (3) raised to the power which is equal to the level number. Additionally, the size of each problem is n/(2^r) where r is the number of the level. Finally, summing over the levels of recursion, we can say that any function satisfying the inequality mentioned in the first paragraph with q > 2 is bounded by O(n^log₂q).

Again the section mentions an alternative method of finding the bound using partial substitution, but I can't honestly say that I understand how this method adds anything that unrolling the substitution will not.

Another case to be considered is one where q = 1. In the first level, there is one problem of size n. Then one problem of size n/2, then one problem of size n/4 and so on down the line. We can see that the amount of work is decreasing. It is clear from analyzing just these few levels that layer r will have size n/2^j and it will contribute cn/2^j to the running time. Finally, summing the levels of recursion will give us T(n) ⇐ 2cn = O(n). Thus, any T satisfying the inequality from paragraph 1 with q = 1 is bounded by O(n).

It is interesting to note these differences in running times all fall around q = 2, with radically different behavior observed when q = 1 and when q = 3. It leads me to wonder what happens when q is a non-integer number between 1 and 2.

Finally, we can consider what happens in the case that the algorithm “divides up the input into two different pieces of size n/2, solves the subproblems by recursion, and then combines the two into an overall solution, spending quadratic time instead for the initial division and final recombining.” This is different from the problems such as mergesort since it takes quadratic time for the division and recombining instead of linear. So the problems take this form: T(n) ⇐ 2T(n/2) + cn². Instinctively, one would like to say that this should be bounded by O(n² log n) however it is actually bounded by O(n²) due to how quickly n² decreases as it is replaced with n/(2^j)