This is an old revision of the document!
Table of Contents
Chapter 5 - Divide and Conquer
Section 5.1 - A First Recurrence: The Mergesort Algorithm
This section introduces the Divide and Conquer algorithms as a whole by starting with the MergeSort algorithm. The text first covers the logic behind the algorithm. We take an input of size n, split this input into two pieces of equal size, solve the two subproblems separately by recursion, and then combine these two solutions to form an overall solution for the initial problem. And we only spend linear time on the division and recombining process. They also lay out the recurrence relation for Mergesort: T(n) ⇐ 2T(n/2)+cn when n>2 and T(2)⇐c.
The text then goes into the two ways we can solve recurrence relations to see the runtime complexity of an algorithm with a structure such as that of Mergesort. The first strategy is unrolling the recurrence and the second is to guess-and-check and prove your guess by means of induction. I far prefer unrolling the recurrence rather than induction. It makes more intuitive sense to me and the book does a good job reinforcing the material covered in class. The text uses the structure of unrolling and induction to prove that the mergesort algorithm runs in O(n log n) time. The text also briefly mentions a method to prove a recurrence relation using partial substitution, but I did not find this nearly as intuitive as simply using a regular inductive argument.
