Chapter 5

Section 5.1 introduces the divide and conquer style of algorithmic problem solving with the Merge-Sort algorithm. The algorithm can be represented by the following recurrence equation: T(n) = 2T(n/2) + cn for all n > 2. This algorithm basically splits the list of items down recursively until it gets to a “base case” where there are only one or two items. The comparison at this point is a simple greater than or less than. The sorted pieces are then combined back together into a full list. The runtime of this algorithm is O(nlogn).

I give this chapter a 6 for readability and a 6 on the interesting scale.

Section 5.2 dives deep into recurrence relations. It stars with by explaining the simple recurrence relation that arose in the mergesort algorithm. The mergesort is a good example since it has two subproblems and the total work per level does not change. As section 5.2 continues into recurrence relations of algorithms with more than two subproblems, we find that the work per level begins to increase, bounding those algorithms in O(n^logq), with q being the number of subproblems the algorithm has. The chapter goes onto show that recurrence relations with only one subproblem run in O(nlogn) time because the work being done decreases every level.

This chapter was cool. I give it an 8 on the interesting scale and a 7 for readability.