So we're almost at the finish line of our analysis of quick sort. Let me remind you what we're proving. We're proving that for the randomized implementation of quick sort where we always choose the pivot element to partition around uniformly at random, we're showing that for every array, every input of length N, the average running time of quick sort over the random choices of pivots is [inaudible] of N log N. So we've done a lot of work in the last couple of videos. Let me just remind you about the stories so far. In the first video what we did is we identified the relevant random variable that we cared about, capital C, the number of comparisons that Quicksort makes among the pairs of elements in the input array. Then we applied the decomposition approach. We expressed capital C, the overall number of comparisons, as a sum of indicator or 0-1 random variables. For each of those variables XIJ, just counted the number of comparisons involving the Ith smallest and Jth smallest entries in the array, and that's gonna be either zero or one. Then we applied linearity of expectation to realize, all we really needed to understand was the comparison probabilities for different pairs of elements. [inaudible]. Second video we nailed what that comparison probability is, specifically, for the I smallest and the J smallest elements in the array, the probability that quick sort compares them when you always make random [inaudible] choices is exactly. Two divided by the quantity J minus I. Plus one. So putting that all together, yields the following expression, governing the average number of comparisons made by quick sort. One thing I want you to appreciate is, is in the last couple of videos, we've been sort of amazingly exact as algorithmic analysis goes. Specifically we've done nothing sloppy whatsoever. We've done no estimates. The number of comparisons that quick store makes on average is exactly this double sum. Now surely we'll do some inequalities to make our lives a little bit easier. But up to this point everything has been completely exact. And this will actually see why there's small constants in the, in the, in quick sort. It's basically going to be this factor two. Now the next question to ask is, what are we shooting for? Remember the theorem we want to prove is that the expected number of comparisons really the expected run time is all of N log N, so we're already done. Well not quite we're gonna have to be a little bit clever, so if we're looking at this double sum, and we ask how big are the sum ends and how many terms are there? Well the biggest sum ends we're ever going to see are when I and J are right next to each other when J is one bigger than I, and in that case this fraction is gonna be one half. So the terms can be as big as one half, how many terms are there? Well there's a quadratic number of terms. So it would be very easy to derive an upper bound that's quadratic in N, but that's not what we want. We want one that's N log N. So to drive that, we're gonna have to be a little bit more clever about how we evaluate this sum. So, the idea is, what we're going to do, is to think about a fixed value of I in this outermost sum. And then we're gonna ask, how big could the inner sum be? So let's fix some value of I, the value of the index in the outer sum. And then let's look at the inner sum, where J ranges from I plus one up to N, and the value of the sum end is one over the quantity J minus I plus one. So how big can this be? Well, let's first understand what the terms actually are. So J starts at I plus one and then it ascends to N. And as J gets bigger the denominator gets bigger. So the sum ends get smaller. So the biggest sum end is gonna be the very first one. And J is as small as possible. Namely I plus one. When J is I plus one the sum end is one half. Then J gets incremented in the sum. And so that's, we're gonna pick up a one third term followed by one fourth term, and so on. So there's gonna be, for every inner sum is gonna have a this form, one-half plus one-half equals one-fourth. And then it's gonna sort of run out at some point, when J equals N. And the biggest term we're ever going to see is gonna be a one over N, in the case where I equals one. So. Let's make our lives easier by taking this expression we started with. Star, and instead of having a double sum, let's just upper bound this with a single sum. So what are the ingredients of a single sum? Well, there's this two, can't forget the two. Then there's N choices for I, actually, there's N minus one choices for I, but let's just be sloppy and say N choices. So that gives us a factor N. And then how big can an inner sum be? Well, inner sum is just a bunch of these terms, one-half plus one-third and so on. The biggest of those inner sums is the one occurring when I equals one, at W, at which point the last term is one over N. So, we're gonna just do a change of variable and express the inner [inaudible], upper bound on each inner sum as the sum from K equal two to N of one over K. So that's looking more manageable just having the single sum involving this index K, and life's gonna get really good when we prove the next claim, which is that this sum cannot be very big, it's only logarithmic in N, even though there's a linear number of sum N's, the overall value of the sum is only logarithmic. That, of course, is gonna complete the proof, 'cause that'll give us an overall bound of two times N times the natural log on N. So it's an N login bound with really quite reasonable constants. So, why is this true? Why is this sum only logarithmically large? Well, let's do a proof by a picture. I'm going to write this sum. In a geometric fashion. So on the X axis, let me mark off points corresponding to the positive integers. And on the Y axis, let me mark off points corresponding to fractions of the form, one over K. And what I?m gonna do is gonna draw a bunch of rectangles. Of decreasing area, specifically they all have with one, and the heights are gonna be like one over K. So the area of this guy's one, the area of this guy's one half, the area of this guy's one third, and so on. And now I'm going to overlay on this picture the graph of the function, the continuous function, F of X equals one over X. So notice that is going to go through these three points. It's gonna kiss all of these rectangles on their upper right corners. Now what is it we're trying to prove? The claim we're trying to prove is that this sum, one half plus one third and so on, is upper bounded by something, so the sum can be just thought of as the areas in these rectangles, the one half, the one third and so on, and we're going to upper bound it by the area under the blue curve, if you notice the area under the blue curve is at least as big as the sum of the areas of the rectangles because the curve hits each of these rectangles in its north east corner. So putting that into mathematics, the sum from K equal two to N of one over K. Is met in above by the integral. And we'll start the area of the curve at one. And then we need it to go all the way up to N. Of the function one over X. The X, so that's the area under the curve. And if you remember a little bit of calculus the integral of one over X is the natural log of X. So this equals the natural log of X. Evaluated at one. Also known as login minus log one. And of course log one would be zero, so that gives us our login. So that completes the proof of the claim. That indeed, the sum of these one over K's is bounded above by the natural log of N, and that in fact completes the proof of the theorem. You've got to be the expected number of comparisons, at most two N times this sum, which is at most log N. And altogether, we find that the expected number of comparisons that quick sort makes on an arbitrary input of length N. Is two times N times the natural log of N. So that would be big o of N, log N, with quite reasonable constants. Now, this is just the number of comparisons, but as we observed earlier, the running time of Quicksort on average is not much more than that, the running time is dominated by the number of comparisons that it makes. Moreover, as we discussed when we were talking about the details of the implementation, it works in place, essentially no extra storage is necessary. So that is a complete and mathematically rigorous explanation of just why Quicksort. Is so quick.
