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.
