Chapter 5 – Divide and Conquer

Mergesort sorts a list by dividing it in half, sorting each half separately using recursion, and combining the two sorted lists. This is a template for many divide-and-conquer algorithms:

  "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."

These types of algorithms need a base case. We then need to denote T(n) as the worst-case running time for a given problem of this type. We then break this running time down as the algorithm divides and conquers and we end up with a recurrence relation. There are two basic ways to solve a recurrence: 1.) “unroll” the recursion; and 2.) guess and check.

Looking at Mergesort as an example, we can see how the process of unrolling takes place: we must identify a pattern in the running time across the first few levels, sum the running times over all levels, and arrive at a total running time. We can see that the first level of Mergesort has a problem of size n and takes at most cn time plus all the time spent in remaining recursive calls, the next level has two problems of size n/2, taking at most cn/2, two times, so cn/, etc. To identify a pattern, we see than at level j, there are now cn/2^j problems 2^j times, which is simply cn. We then sum over all levels of recursion and see it takes log₂n times to half the input to bring it from size n to size 2 (our base case). Since we are doing cn work at every level, the total running time is O(nlogn).