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.

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

This problem occurs when trying to analyze rankings. Websites such as Facebook use this method when trying to find things one might “like”. A problem that arises is when one must compare two rankings. To qualify this, we can count the number of inversions. An inversion occurs if indices i<j have the values ai>aj, and are not in order.

We can count the inversions in O(n log n) time. First, we divide the list into two pieces, and count the number of inversions in each half separately. Then, we count the number of inversions between the two halves. This routine is known as Merge-and-Count. When comparing the two lists, we take the smaller one and append it to a new list.