Chapter 5

This chapter deals with the Divide and Conquer problems involving recurrence relations.This method can sometimes improve O(n^2) time to O(nlogn) time.

This section introduces the first example in Divide and Conquer: mergesort. The idea of mergesort is to keep dividing a problem into two equal sizes, till the running time of dealing with the problem becomes constant, that is to T(2)⇐c. We need to find the relationship between each level of “division”, that is to T(2)⇐c. In order to achieve that, we need to find the running time used to join two parts together in each level, which is actually cn. Hence, we have: T(n)⇐2T(n/2)+cn. Two ways of analyzing the running time: 1, gradually “unroll” the recursion; 2, guess a solution. For the 1st method, the idea is to figure out the pattern of running time for each level and sum them up at the end. For the 2nd method, if we have good intuition, we simply plug in the guessed result and see if it satisfies our inequality. A stronger version of guessing is that we guessed out all the relevant constants. A weaker version is we leave the constants unknown and figure it out along the way. A natural “question” is, how do we attain such intuition? :P Readability is 6.

A more general case of the mergesort problem than dividing problem by 2 each time is dividing problem by q each time. Then the recurrence relationship becomes: T(n)⇐qT(n/2)+cn and T(2)⇐c The approach of analysing the running time in the “unrolling” way is similar with that presented in section 1: analyse a few levels and then identify a pattern, and then sum up all levels of recursion. The “guessing” way becomes more interesting in this case. Because the connecting time cn cannot cancel with anything here. Therefore, we slightly adjust the guess from kn^d to kn^d-ln so that the ln will do the cancellation. If we have a very special case, q=1, it is not hard to show that the running time is bounded by O(n). A related problem is to change the recurrence relationship a little: T(n)⇐2T(n/2)+O(n^2), from unrolling the recurrence we obtain that the bound of the running time os O(n^2). I wonder what application does this relationship has. Readability is 7, the modification of guessing part is fun to read.

This section talks about a concrete example using divide and conquer–counting inversion. The problem is to count how many inversions are there in a sequence of n numbers. The brute-force way is to check each pair which has a bad running time O(n^2). We want to use the divide and conquer method to improve the running time. What we do the merge-sort + count-sort algorithm. Basically, we look at two already sorted list and see how many inversions there are if combine them together-which can be counted in linear time when using a counter, then sort the combined list to add together with the other combined sorted list. The running time is then O(log(n)n) since the recurrence relationship is the T(n)⇐2T(n/2)+cn one. I think this way of counting inversion is smart. Readability is 7.