Chapter 5

This section begins the chapter meant to break down and discuss several divide and conquer algorithms. We begin with the familiar Mergesort. This algorithm involves breaking up the input into smaller groups, organizing each group, and putting them back together. To use the book's words. The underlying concept is “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.” There are two main ways to solve a recurrence. The first is to unroll the recursion. The second way is guess and check. To unroll a recursion, first you analyze the first few levels of the recursion. Then we identify a pattern. Then, we sum over all levels of recursion.