This is an old revision of the document!
Table of Contents
Chapter 5: Divide and Conquer
Section 1: A First Recurrence: The Mergesort Algorithm
'The Mergesort Algorithm sorts a given list of numbers by first dividing them into two equal halves, sorting each half separately by recursion, and then combining the results of these recursive halves.' The abstract behavioral template for many common divide-and-conquer algorithms is this: 'Divide the input into two pieces of equal size; solve the two subproblems on these pieces separately by recursion; and then combine the two results into an overall solution, spending only linear time for the initial division and final recombining.' This type of recursive methodology requires a base case, having it 'bottom out' on inputs of some constant size. In the case of Mergesort, once input has been reduced to size 2, we stop the recursive process and sort the two elements in one comparison. For each recursive algorithm, there is a recursive relation to describe its processes. It follows the formula T(n) = cT(k) + O(l), where c is the number of subproblems, k is the factor by which the input size decreases, and l is the cost of recombining the subproblems into a single problem. The two basic ways to go about solving a recurrence are: 1) unrolling the recursion, accounting for the running time of across the first few levels and identifying a pattern of the recursion, and then summing the run times of all the levels to find the total run time, and 2) Start with a guess for the solution, substitute into the recurrence relation, and check that it works. For 1), we first analyze the first few levels, identify a pattern, and then sum over all levels of recursion. 'Any function T(-) satisfying T(n) ⇐ 2T(n/2) + O(n) is bounded by O(nlogn), when n > 1. For 2) we first take our guess for what the run time is, plug it into the recurrence relation, and check to see if completes the induction argument. There is also a weaker form of substitution when we are unsure of the whole run-time of our guess. This section was very easy to understand having talked about it in class, and given prior experience with the Mergesort Algorithm. I would give it a 9/10.
