0:00

In this video we'll be giving a running time analysis of the merge sort algorithm.

Â In particular, we'll be substantiating the claim that the recursive divide and

Â conquer merge sort algorithm is better,

Â has better performance than simple sorting algorithms that you might know,

Â like insertion sort, selection sort and bubble sort.

Â So in particular, the goal of this lecture will be to,

Â mathematically argue the following claim, from an earlier video.

Â That, in order to sort an array of n numbers,

Â the merge sort algorithm needs no more than a constant times n log in operations.

Â That's the maximum number of lines of code it will ever execute.

Â Specifically 6 times n log n + 6n operations.

Â So how are we going to prove this claim?

Â We're going to use what is called a recursion tree method.

Â The idea of the recursion tree method is to write out all over the work done by

Â the recursive merge sort algorithm in a tree structure with the children

Â of a given node corresponding to the recursive calls made by that node.

Â The point of this tree structure is it will facilitate a interesting way to count

Â up the overall work done by the algorithm and will greatly facilitate the analysis.

Â So specifically what is this tree?

Â So at level zero we have a root.

Â 1:14

And this corresponds to the outer call of merge sort, okay so

Â I'm going to call this level zero.

Â Now, this tree is going to be binary in recognition of the fact that

Â each invocation of MergeSort makes two recursive calls.

Â So the two children will correspond to the two recursive calls of MergeSort.

Â So, at the root we operate on the entire input array, so let me draw a big

Â array indicating that, and at level one we have one sub problem for the left half and

Â another sub problem for the right half of the input array.

Â And I'll call these first two recursive calls level one.

Â Now, of course, each of these two level one recursive calls will

Â themselves make two recursive calls.

Â Each operating on then a quarter of the original input array.

Â So those are level two recursive calls of which there are four.

Â And this process will continue until eventually the recursion bottoms out

Â in base cases when there's only an array of size zero or one.

Â So now I have a question for you which I'll give you in the form of a quiz.

Â Which is at the bottom of this recursion tree corresponding to the base cases,

Â what is the level number at the bottom?

Â So at what level do the leaves in this tree reside?

Â 2:22

Okay, so hopefully you guessed, correctly guessed that the answer is the second one.

Â So namely that the number of levels of the recursion tree is essentially logarithmic

Â in the size of the input array.

Â The reason is basically that the input size is

Â being decreased by a factor two with each level of the recursion.

Â If you have an input size of n at the outer level, then each of the first set of

Â recursive calls operates on a array of size n over 2.

Â At level two, each array has size n over 4 and so on, whereas if the recursion bottom

Â out, well, down at the base cases, where there's no more recursion,

Â which is where the input array has size one or less.

Â So in other words, the number of levels of recursion is exactly the number of

Â times you need to divide n by 2, until you get down to a number that's most one.

Â And recall, that's exactly the definition of a logarithm base 2 of n.

Â So since the first level is level zero and the last level is level log base 2 of n.

Â The total number of levels is actually log base 2 of n plus 1.

Â And when I write down this expression I'm here assuming that n is a power of 2 which

Â is not a big deal.

Â I mean the analysis is usually extended to the case where n is not a power of 2.

Â But this way we don't have to think about fractions log base 2 of n

Â then is an integer.

Â Okay, so let's return to the recursion tree, and

Â let me just redraw it really quick.

Â 3:39

So again, down here at the bottom of the tree, we have the leaves.

Â And i.e., the base cases, where there's no more recursion.

Â Which, when n is a power of 2, correspond exactly to single element arrays.

Â 3:51

So that's the recursion tree corresponding to an invocation of MergeSort.

Â And the motivation for writing down, for organizing the work performed by MergeSort

Â in this way, is it allows us to count up the work level by level.

Â And we'll see that's a particularly convenient way to account for

Â all of the different lines of code that get executed.

Â Now to see that in more detail, I need to ask you identify a particular pattern.

Â So first of all, the first question is, at a given level j of this recursion,

Â exactly how many distinct sub problems are there as a function of the level j.

Â That's the first question.

Â The second question is, for

Â each of those distinct sub problems at level j, what is the input size.

Â So what is the size of the array which is passed to a subproblem

Â residing at level j of this recursion tree?

Â 4:42

So first of all at a given level j,

Â there's precisely 2 to the j distinct subproblems.

Â There is one outermost subproblem at level zero.

Â It has two recursive calls.

Â Those are the subproblems at level one, and so on.

Â In general, since MergeSort calls itself twice,

Â the number of subproblems is doubling each level, so

Â that gives us the expression 2 to the j for the number of subproblems at level j.

Â 5:05

On the other hand via a similar argument the input size is halving each time

Â with each recursive call you pass at half of the input that you were given.

Â So at each level of the recursion tree

Â we're seeing half of the input size of the previous level.

Â So after j levels since we started with an input size n after j levels

Â each subproblem will be operating on an array of length n over 2 the j.

Â Okay so now let's put this pattern to use, and

Â actually count up all of the lines of code, and thenMergeSort executes.

Â And as I said before, the key idea is to count up the work level by level.

Â Now to be clear, when I talk about the amount of work done at level j.

Â What I'm talking about is the work done by those 2 to the j invocations of MergeSort

Â not counting their respective recursive calls,

Â not counting work which is going to get done in the recursion lower in the tree.

Â Now recall merge sort is a very simple algorithm, it just three lines of code,

Â first there's a recursive call so

Â we're not counting that, second, there's another recursive call.

Â Again, we're not counting that at level j.

Â And then third, we just invoke the merge subroutine.

Â So really outside the recursive cause all that MergeSort

Â does is a single indication of merge.

Â Further, recall we already have a good understanding of the number of lines of

Â code that merge needs.

Â On an input of size m, it's going to use at most 6m lines of code.

Â That's an analysis that we did in the previous video.

Â So let's fix a level j.

Â We know how many subproblems there are, 2 to the j.

Â We know the size of each subproblem, n over 2 to the j.

Â And we know how much work merge needs on such an input.

Â We just multiply by 6.

Â And then we just multiply it out.

Â And we get the amount of work done at a level j.

Â Okay at all of the little j subproblems, so here it is in more detail.

Â 6:54

We also observed that each level j subproblem is past

Â an array as input which has length n over 2 to the j.

Â And we know that the merge subroutine, when given an array of size

Â n over 2 to the j, will execute at most 6 times that many number of lines of code.

Â So to compute the total amount of work done at level j,

Â we just multiply the number of problems times the work done per subproblem.

Â And then something sort of remarkable happens.

Â We get this cancellation of the two 2 to the j's and we get an upper bound

Â 6n which is independent of the level j.

Â So we do at most 6n operations at the root.

Â We do at most 6n operations of level one, at level two, and so on okay.

Â It's independent of the level.

Â Morally, the reason this is happening because of a perfect equilibrium between

Â two competing forces.

Â First of all,

Â the number of subproblems is doubling with each level of the recursion tree.

Â But secondly, the amount of work that we do per subproblem is halving with each

Â level of the recursion trees.

Â And so those two cancel out.

Â We get an upperbound 6n, which is independent of the level j.

Â Now, here's why that's so

Â cool, right, we don't really care about the amount of work just at a given level.

Â We care about the amount of work that MergeSort does ever at any level.

Â But if we have a bound on the amount of work at a level which is independent of

Â the level, then our overall bound is really easy.

Â What do we do?

Â We just take the number of levels.

Â And we know what that is.

Â It's exactly log base 2 of n + 1.

Â Remember, the levels are zero through log base 2 of n inclusive.

Â And then we have an upper bound 6n for each of those log n plus 1 levels.

Â So, if we expand out this quantity, we get exactly the upper bound that was claimed

Â earlier, namely that the number of operations MergeSort executes

Â is at most 6n times log based 2 of n plus 6n.

Â So that my friends, is a running time analysis of the merge sort algorithm.

Â That's why its running time is bounded by a constant times nlogn,

Â which especially has n grows large, it is far superior to the more simple

Â iterative algorithms like insertion or selection sort.

Â