This is an old revision of the document!
Table of Contents
Chapter 5: Divide & Conquer
Divide and conquer deals with breaking inputs into parts, solving recursively, and then combining solutions.
5.1 - A First Recurrence: The Mergesort Algorithm
Mergesort sorts a given list of numbers by first dividing them into two equal halves, sorting each half separately by recursion, and then combining the results of these recursive calls using the linear-time algorithm for merging sorted lists.
Two ways to find solutions for recurrence: The first is to ‘unroll’ the recursion and identify a pattern. The sum of the running times over all levels of recursion arrive at a running time. The second is to begin with a guess, substitute it into the recurrence relation, and verify.
Unrolling the Mergesort Recurrence: At first level, the problem is size n (cn + subsequent calls). The next level has two problems with size n/2 (cn/2 + subsequent calls), then four problems with size n/4 (cn/4 + sub calls), etc. The pattern is defined by n/2^j (j = level). Thus level j contributes 2^j(cn/2^j) = cn to the running time. The total running time for the algorithm is O(n log n).
5.2 - Further Recurrence Relations
In the case of a tree where q > 2 (q being number of children), the work increases with every level of recursion. This gives q^j instances at level j. A function with q > 2 is bounded by O(n^log2(q)). For example, when q=2, running time is O(n^4).
Consider the case where q=1. The work per level decreases with recursion. At an arbitrary level j, it contributes cn/2^j to the run time. A function with q=1 is bounded by O(n) run time.
q = 1: O(n) - linear q = 2: O(n log n) q > 2: polynomial with exponent > 1
5.3 - Counting Inversions
An inversion occurs when an ordering of numbers has numbers out of order. There may be a quadratic number of inversions for each set of numbers. The algorithm is similar to Mergesort except we count inversions along with sorting the list. Recursively divide the list and sort separate halves. Compare the sorted halves against each other for inversions.
When merging the list, we compare elements in subsets A and B. If the element in A is smaller, it is appended to the new list and no inversions occur. If B is smaller, it is appended to the list and the number of remaining elements in A is the number of inversions because they come before elements in B. This is the Sort-and-Count algorithm runs in O(n log n) time.
