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