Chapter 5 – Divide and Conquer

My notes on the assigned sections of Chapter 5 of Algorithm Design by Jon Kleinberg and Éva Tardos. This chapter details divide and conquer algorithms. A divide and conquer algorithm “breaks the input into several parts, solves the problem in each part recursively, and then combines the solutions” into an overall solution.

In the Mergesort algorithm, we divide the input into 2 pieces of equal size and solve the 2 subproblems. After solving the 2 halves by recursion, we combing the 2 results into an overall solution, spending linear time for everything. The recurrence relation for Mergesort is T(n) ⇐ T([n/2]) + T([n/2]) + cn. To solve such a recurrence you can either unroll the recursion or guess for the solution, substitute it into the recurrence relation, and then check and see if it works. Unrolling seems to be the most intuitive. Unrolling the recursion, we get that Mergesort takes O(nlogn).

Overall this section was very readable and interesting. I'd give it a 9/10 for both.