DinS Written on 2017/12/10
Divide & Conquer is a prototype for algorithm design. The paradigm can be summarized as follows:
(1) Divide original problem into smaller sub-problems.
(2) Conquer via recursive calls.
(3) Combine solutions of sub-problems into one for original problems, i.e. clean-up work.
Here we’ll introduce MergeSort as a demonstration of Divide & Conquer algorithm.
1. An instance of MergeSort
2. What is MergeSort doing?
Basically, there’re two steps in MergeSort. First we keep splitting the input array in half until we get only single element. Since there’s only one element, it is sorted by default. Next we keep merging these sorted arrays to get bigger sorted arrays. When we’ve merged all the elements, we end up with a sorted array.
The main problem is how to get bigger sorted array from small arrays. In other words, how do we merge? In fact this is not hard at all. Assuming we have two sorted arrays, A and B, we just compare each element in both arrays from beginning to end. Each comparison will give a smaller element. We put it in another array C. After all elements in both arrays are done, the C is a sorted array. See an example below.
As you can see, all elements in A and B are scanned once and only once. This gives O(n), if n is defined as the size of A and B.
3. Running time for MergeSort – a rough guess
Before formal analysis, we can first take a guess on the running time.
For the splitting step, split itself takes O(1) time. How many times do we have to split? Well, we can think backward. The final result would be each element on its own. You have to split n times to make each element alone. So that’s O(n).
For the merging step, we know that regardless of what array to merge, all elements are scanned once and only once. Why is it? You can look at the visual example above to get the idea. On each layer, all elements appear. This means that for each layer, we use O(n) to merge. The next question is how many layers do we have? Think it this way. We expand the number of elements twice to advance to next layer. So the question becomes if we keep multiplying 2 each round, how many rounds need we have to get from 1 to n? To express this idea in math, we have 2i = n. That i is the round we need to do. As a result i = log2n. In other word, we’ll have O(logn) layers. All in all, the merge step takes O(nlogn) times. The total time for MergeSort would be O(n + nlogn) = O(nlogn).
4. Running time for MergeSort – a formal proof
First let’s find out the running time for a single merge. Given array A and B both of size m, we need to scan through A and B. That’s 2m. We’re also copying each element from A and B to C. That’s also 2m. All in all, we use roughly 4m to do a single merge.
Next let’s generalize the recurrence a bit. Look at this tree below.
We keep splitting the original problem by half. The result would be subproblems are growing at twice each level, and size of problem is shrinking by half each level. The claim is on level j, the number of subproblems will be 2j, and problem size will be 
for each subproblem.
From this claim we can work out the total number of operations at level j. That number will be the number of subproblems times the running time for each subproblem. In a more formal statement:
Number of operation at level 
That 4m is the time for a single merge. We simply substitute m with the real problem size. The outcome is 4n, independent of j.
Since on each level we need 4n, and we have log2(n+1) level, that gives us 4n(log2n + 1), which O(nlogn).
5. Running time for MergeSort – a still more formal proof
We’ll use equations to solve the running time for MergeSort directly.
From the method of MergeSort, we can get these two equations.
T(n) = 2T(n/2) + O(n) ①
T(1) = O(1)
I’ll explain a bit. T(n) is the total number of operations for MergeSort. Since we’re splitting the original problem in half and apply MergeSort to each subproblem again, that is 2T(n/2). That “2” is applying MergeSort to the two subproblem. That “n/2” represents the shrinking of problem size. We have analyzed that we need O(n) to do the merging. That final O(n) is the merging.
T(1) = O(1) should be simple. When there’s only one element, it’s sorted by default. We need O(1) to sort it.
From these two equations we can solve for T(n) in regard of n. How? The trick is using T(n) repeatedly.
The first equation is T(n) = 2T(n/2) + O(n). There’s a T(n/2) we don’t know. Don’t worry. We can substitute n with n/2 in this equation. If we do this, we get
T(n/2) = 2T(n/4) + O(n/2) ②
Now that we’ve got T(n/2), we can substitute it in ① and this gives us
T(n) = 4T(n/4) + 2O(n/2) + O(n) = 4T(n/4) + 2O(n) ③
What about T(n/4)? We can use the same trick again. Substitute n with n/4 in ① and we get
T(n/4) = 2T(n/8) + O(n/4) ④
Now using ④ we can write ③ as this
T(n) = 8T(n/8) + 4O(n/4) + 2O(n) = 8T(n/8) + 3O(n)
We can still use this trick, but for now we can see something there. In fact we can generalize the equation to something like this.
OK, but we haven’t solved it. We need to use the second equation T(1) = O(1). How can we make T(1)? Easy. If 
, we can get it. To Make it happen, we need 2i = n, which means i = log2n.
Now we just substitute i with log2n, and we get this.
We simplify a bit and get
T(n) = n*O(1) + log2n * O(n) = O(n) + O(logn)*O(n) = O(n + nlogn) = O(nlogn)