Chapter 5

Mergesort's behavior can be described as dividing the input into two halves, solving each half separately by recursion, and then combining the two results into an overall solution. So, it takes O(n) time dividing the input in half, T(n/2) time to solve each half, then O(n) time to combine the two solutions back together. Thus, the recurrence relation is 2T(n/2) + O(n). This itself is not a run time, however. In order to determine the run time of an algorithm from a recurrence, we can either “unroll” the recurrence or simply guess. In the case of Mergesort, the run time is O(nlogn). The overall readability of this section was 6/10.

There are various other recurrence relations that correspond to different Divide and Conquer algorithms. For instance, Mergesort divides its input into q=2 subproblems of n/2 size, but other algorithms can have q>2 subproblems. Such a recurrence relationship would look like qT(n/2) + cn (or O(n)). Question: What is the difference between writing O(n) or cn in the recurrence relationship? A relationship with only q=1 subproblems would simply be T(n/2) + cn, which translates to O(n) run time. However, not all recurrences can combine two subproblems in O(n) time. In some instances it can simply be O(1), and in others, like in decaying geometric sums, it can be O(n^2). Thus, there are many different possible recurrence relationships for Divide and Conquer algorithms. The readability of this section is 4/10 because it involved a lot of complex math.