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.

The motivation of the problem is preference rankings. Suppose we wish to create an algorithm that compares the rankings of one individual to another's. Similar rankings have very little differences, and different rankings have, obviously, a great deal of differences. In this sense, when comparing two rankings we wish to count the number of inversions as an indication of how similar/different the two rankings are. An algorithm that performs this type of comparison can run in O(nlogn) time. This algorithm makes use of a routine called Merge-and-Count, which takes two sorted lists A and B and both simultaneously adds elements from A and B into a combined sorted list C and counts the number of inversions. This itself takes O(n) time but is only one part of the overall algorithm.

Sort-and-Count(L)

if list L has one element
 return 0 and the list L
Divide the list into two halves A and B
(iA, A) = Sort-and-Count(A)
(iB, B) = Sort-and-Count(B)
(i, L) = Merge-and-Count(A, B)
total_inversions = iA + iB + i
return total_inversions and the sorted list L

Overall, the readability of this section is 7/10.