This is an old revision of the document!
Table of Contents
Chapter 5: Divide and Conquer
5.1: A First Recurrence: The Mergesort Algorithm
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.
5.2: Further Recurrence Relations
Like Mergesort, there is a general class of algorithms that have recursive calls on q subproblems of size n/2 and then combine results in O(n) time.
For the case of q>2, however, we unroll this following the previous style. First, we analyze the first few levels, and then identify a pattern. Finally, we apply a partial substitution.
When q=1, the outcome is entirely different, however, we still solve the problem the same way. We can sum this up as any function with q=1 is bounded by O(n).
