Chapter 5: Divide and Conquer

The Mergesort Algorithm shows the general approach to analyzing divide-and-conquer algorithms. Mergesort can be summarized as follows: “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” (210).

Any algorithm that fits this pattern would spend O(n) time dividing the input into two pieces with a size of n/2. It then spends the worst-case running time, T(n/2) dividing each of those sections, finally running in O(n) time to combine the solutions. This is an example of a recurrence relation: T(n) ⇐ 2T(n/2) + cn or as T(n)⇐ 2T(n/2)+ O(n). The most natural way to find a recurrence solution is to “unroll” the recursion. Another way is to use substitution and then induction.

Unrolling Mergesort, we see that it takes at most cn plus the time in all subsequent calls. The next level therefore takes cn/2, totaling to at most cn, and so on and so on. This allows us to identify a pattern and then sum it over all levels of recursion, which if we have cn work over log n levels, it gives us a runtime of O(n log n).

We can also solve this problem using substitution or partial substitution.