So this is the first video of three in
which we'll mathematically analyze the
running time of the randomized
implementation of quicksort. So in
particular we're gonna prove that the
average running time of quicksort is big-O
of n log n. Now this is the first
randomized algorithm that we've seen in
the course and therefore, in its analysis
will be the first time that we're gonna
need any kind of probability theory. So
let me just explain upfront what I?d like,
expect you to know in the following
analysis. Basically I need you to know the
first few ingredients of discrete
probability theory, so I need you to know
about sample spaces, that is how to model
all of the different things that could
happen, all of the ways that random
choices could resolve themselves. I need
you to know about random variables,
functions on sample spaces which take on
real values, I need you to know about
expectations that is average values of
random variables, and Very simple but very
key property we're going to need in the
analysis of qucksort is linearity of
expectation of expectation. So, if you
haven't seen this before or if you're too
rusty, definitely you should review this
stuff before you watch this video. Some
places you can go to get that necessary
review, you can look at the probability
review part one video that's up on the
course. If you prefer to read something,
like I said at the beginning of the
course, I recommend the free online
lecture notes by Eric Lehman and Tom
Laten. Mathematics for Computer Science.
That covers everything we'll need to know
plus much more. There's also a wiki book
on dist. Probability with is a perfectly
fine obviously free-source unless you can
learn the necessary material. Okay? So
after you've got that sorta fresh in your
minds and you're ready to watch the rest
of this video, and in particular we're
ready to prove the following theorems
stated in the previous video. So, the
quick sort of algorithm with a randomized
implementation, that is wherein every
single recursive sub call you pick a pivot
uniformly at random restated the following
assertion. But for every single input so
for a worse case input a ray of length n,
the average running time of quick sorts.
With the random pivots. Is O of N login.
And again, to be clear where the
randomness is, the randomness is not in
the data. We make no assumptions about the
data, as per guiding principles. No matter
what the input array is, averaging only
over the randomness in our own code. The
randomness internal to the algorithm, we
get a running time of N log N. We saw in
the past that the best case behavior of
Quick Sort is N log N. The worst case
behavior is N squared. So this theorem is
asserting that, no matter what the input
array is, the typical behavior of Quick
Sort is far closer to the best case
behavior than it is to the worst case
behavior. Okay so that's what we are going
to prove, in the next few videos. So let's
go ahead and get started. So first I'm
going to set up the necessary notation and
be clear about exactly what is the sample
space what is the random variable that we
care about and so on. So we're gonna fix
an arbitrary array of length n, that's
gonna be the input to the quick sort
algorithm. And we'll be working with this
fixed but arbitrary input array for the
remainder of the analysis. Okay, so just
fix a single input in your mind. Now
what's the relevant sample space. Well
recall what a sample space is. It's just
all the possible outcomes of the
randomness in the world. So it's all the
distinct things that could happen. Now
here the randomness is of our own
devising, it's just a random pivot
sequences. The random pivots chosen by
quick sort. So omega is just a set of all
possible random pivots that quick sort
could choose. Now the whole point of this
theorem proving that the average, average
running time it puts is sort of small,
boils down to computing the expectation of
a single random variable. So here's the
random variable we're going to care about.
Four Given pipit sequence, remember that
random variables are real valued functions
defined on the sample space. So for a
given point in the sample space, or pipit
sequence sigma, we're going to define
capital C of sigma, as the number of
comparisons that Quick Sort makes, where
by comparison I don't mean something like
within array index in a four loop, that's
not what I mean by comparison. I mean,
comparison between two different entries
of the input array, by comparing the third
entry in the array against the seventh
entry in the array to see whether the
third entry or the seventh entry is
smaller. Notice that this is indeed a
random variable that is given knowledge of
the pivot sequence sigma. The choices of
all pivots you can think a quick sort at
that point is just a deterministic
algorithm, with all of the pivot choice
predetermined. So the deterministic
version of quick sort makes some
deterministic number of comparisons. So,
if we're given pivot sequence sigma, we're
just calling C of sigma to be whatever,
however many comparisons it makes given
those choices of pivots. Now the, with the
theorem I've stated it's not about the
number of comparisons of Quick Sort but
rather about the running time of Quick
Sort but really, if you think about it
kinda only real work that the Quick Sort
algorithm does is make comparisons between
two, between pairs of elements in the
input array. Yes, there's a little bit of
other book keeping but that's all noise,
that's all second order stuff. All Quick
Sort really does is comparisons between
the pairs of elements in the input array.
And if you want to know what I mean by
that a little more formally, dominated by
comparisons. I mean, that there exists a
constant c, so that the total number of
operations of any type that quick sort
executes is at most a constant factor
larger than the number of comparisons. So
let's say that by RT I mean the number of
primitive operations of any form that
quick sort uses and for every. Pivot
sequence sigma. The total number of
operations is no more than a constant
times. The total number of comparisons.
And if you want a proof of this, it's not
that interesting, so I'm not gonna talk
about it here. But in the notes posted on
the website, there is a sketch, of why
this is true. How you can formally argue
that there isn't much work beyond just the
comparisons. But I hope most of you find
that, to be pretty intuitive. So, given
this, given the, the running time of Quick
Sort boils down just to the number of
comparisons. And we want to prove the
average running time is N log N. All we
gotta do, quote unquote, all we have to
do, is prove that the average number of
comparisons that Quick Sort makes, is O of
N log N. And that's what we're gonna do.
So that's what the, the rest of these
lectures are about. So that's what we
gotta prove. We gotta prove that the
expectation of this random variable C,
which counts up the number of comparisons
quicksort makes is for this arbitrary
input array A of length n, bounded by
big-O of n log n. So the high order bit of
this lecture is a decomposition principle.
We've identified this random variable C,
the number of comparisons, and it's
exactly what we care about. It governs the
average running time of Quick Sort. The
problem is, it's quite complicated. It's
very hard to understand what this capital
C is. It's fluctuating between n log n and
n squared, and it's hard to know how to
get a handle on it. So how are we gonna go
about proving this assertion that the
expected number of comparisons that
quicksort makes is on average just O (n
log n)? At this point we actually have a
fair amount of experience with
divide-and-conquer algorithms. We've seen
a number of examples. And, whenever we had
to do a running-time analysis of such an
algorithm, we wrote out a recurrence, we
applied the master method or, in the worst
case, we wrote out a recursion tree to
figure out the solution of that
recurrence. So you'd be very right to
expect something similar to happen here.
But as we probe deeper and we think about
quicksort, we quickly realize that the
master method just doesn't apply, or at
least not in the form that we're used to.
The problem is twofold. So, first of all,
the size of the two subproblems is random.
Right? As we discussed in the last video
the quality of the pivot is what
determines how balanced a split we get
into the two subproblems. It can be as bad
subproblem size zero and one a size n
minus one. Or it can be as good as a
perfectly balanced split into two
subproblems of equal sizes. But we don't
know. It's gonna be dependent on our range
of choice of the pivot. Moreover the
master at least as we discussed it
required solved subproblems to have the
same size. And unless you're extremely
lucky that's not gonna happen in the
quicksort algorithm. It is possible to
develop a theory of recurrence relations
for randomized algorithms, and to apply it
to quick sort in particular. But I'm not
going to go that route for two reasons.
The first one is its really quite messy.
It gets pretty technical, to talk about
solutions to recurrences for randomized
algorithms, or to think about random
recursion trees. Both of those get, get
pretty complicated. The second reason is,
I really want to introduce you to what I
call a decomposition principle, by which
you take a random variable that's
complicated, but that you care about a
lot. And decompose it in to simple random
variables which you don't really care
about in their own right but which are
easy to analyze and then you stitch those
two things together using linearity and
expectation so that's gonna be the
workhorse for our analysis of the quick
store, of the quick-sort algorithm and
it's gonna come up again a couple of times
in the rest of the course, for example,
when we study hashing. So, to explain how
this decomposition principle applies to
quicksort in particular, I'm gonna need to
introduce you to the building blocks,
simple random variables which will make up
the complicated random variable that we
care about, the number of comparisons. So
here's some notation. Recall that we fixed
in the background an arbitrary array of
length N and that's denoted by capital A
[sound]. And some notation which is
simple, but also quite important by z sub
i. What I mean is the ith smallest element
in the input array capitol A. Also known
as the ith order statistic. So let me tell
you what ZI is not, okay. What ZI is not,
in general, is the element in the
[inaudible] position of the input unsorted
array. What ZI is, is it's the element
which is going to wind up in the
[inaudible] element of the array, once we
sort it, okay. So if you fast forward to
the end of the sorting algorithm, in
position I, you're gonna find ZI. So let
me give you an example. So suppose we have
just a simple array here, unsorted. Were
the numbers six, eight, ten and two, then.
Z one, well that's the first smallest. The
one smallest or just the minimum. So z one
would be the two z two would be the six z
three would be the eight and z four would
be the ten. For this particular input
array. Okay? So z I is just the
[inaudible] smallest number, wherever it
may lie in the original unsorted array
that's what z I refers to. So we already
defined the sample space that's just all
possible choices of pivots, the Quicksort
might make. I already described one random
variable with the number of comparison
that Quicksort makes on a particular
choice of pivots. Now I am getting
introduced a family of much simpler random
variables which count merely the
comparisons involving a given pair of
elements in the input way not all elements
just a given pair. So for a given choice
of pivots given sigma and given choices of
I and J. Both of which are between one and
N. And so we only count things once. I'm
going to insist that I is less than J
always. And now here's a definition. My
XIJ, and this is a random variable, so
it's a function of the pivots chosen. This
is going to be the number of times that ZI
and ZJ are compared in the execution of
quick sort. Okay, so this is gonna be an
important definition in our analysis. It's
important you understand it. So, for
something like the third smallest element
and the seventh smallest element, x I j is
asking, that's when I equals three and j
equals seven, x three seven is asking how
many times those two elements get compared
as quicksort. Proceeds. And this is a
random variable in the sense that if the
pivot choices are all predetermined, if we
think of those being chosen in advance,
then there's just some fixed deterministic
number of times, that ZI and ZJ get
compared. So it's important you understand
these random variables XIJ. So the next
quiz is gonna ask, a basic question about
the range of values that a given XIJ can
take on. So for this quiz we're
considering, as usual, so fixed input
array and now furthermore, fix two
specific elements of the input array. For
example, the third smallest element,
wherever it may lie, and the seventh
smallest element, wherever it may lie.
Think about just these pair of two
elements. What is the range of values that
the corresponding random variable, Xij,
can take on? That is, what are the
different numbers of times that a given
pair of elements might conceivably get
compared in the execution of the quick
sort algorithm? All right so the correct
answer to this quiz, is the second option.
This is not a trivial quiz. This is a
little tricky to see. So the assertion is
that a given pair of elements, they might
not be compared at all. They might be
compared once. And they're not going to
get compared more than once. Okay? So
here, what I'm gonna discuss is why it's
not possible for a given pair of elements
to be compared twice during the execution
of quick sort. It'll be clear later on, if
it's not already clear now, that both zero
and one are legitimate possibilities. A
pair of elements might never get compared
and they might get compared once. And
we'll, and again, we'll go into more
detail on that in the next video. So, but
why is it impossible to be compared twice?
Well, think about two elements. Say, the
third element and the seventh element. And
let's recall how the partition subroutine
works. Observe that in quick sort, the
only place in the code where comparisons
between pairs of the. Input array elements
happens, it only happens in the partition
subroutine. So that's where we have to
drill down. So what are the comparisons
that get made in the partition subroutine?
Well. Go back and look at that code. The
pivot elements is compared to each other
element in the input array exactly once.
Okay, so the pivot just hangs out in the
first entry of the array. We have this for
loop, this index j, which marches over the
rest of the array. And for each value of
j, the j element of the input array gets
compared to the pivot. Okay. So
summarizing in an invocation of partition,
every single comparison involves the pivot
element, okay. So two elements get
compared if and only if one is the pivot.
Alright, so let's go back to the question.
Why can't a given pair of elements in the
[inaudible] get compared two or more
times? Well, think about the first time
they ever get compared in Quick Sort. It
must be the case that at that moment,
we're in a recursive call where either one
of those two is the pivot element. So it's
the third smallest element or the seventh
smallest element. The first time those two
elements are compared to each other,
either the third smallest or the seventh
smallest is currently the pivot, because
all comparisons involve the pivot element.
Therefore. What's gonna happen in the
recursion, well the pitted is excluded
from both recursive calls. So for example
if the second smallest element is
currently the pitted that's not gonna be
passed on to recursive call which contains
the third smallest element. Therefore if
you compared once, one of the elements
that's pitted and it will never be
compared again because the pitted will not
even show up in any future recursive
calls. Okay, so that's the reason. You
compared once, one is the pitted, it
doesn't get passed to the recursion,
you're done, never seen again. So a random
variable which can only take on the value
zero or one is often called an indicator
random variable, because it's in, just
indicating whether or not a certain thing
happens. So, in that terminology, each x I
j. Is indicating whether or not the ith
smallest element in the array, and the jth
smallest element in the array, ever get
compared. It can't happen more than once.
It may or may not happen, and Xij is one
precisely when it happens. So that's the
event that it's indicating. Having defined
the building blocks I need, these
indicator random variables, these X, I,
Js, now I can introduce you to the
decomposition principle as applied to
Quick Sort. So there's a random variable
that we really care about which is denoted
capital C, the number of comparisons the
Quick Sort makes, that's really hard to
get a handle on in and of itself. But we
can express C as a sum of indicator random
variables of these X, I, Js and those, we
don't care about in their own right,
they're gonna be much easier to
understand. So, let me just rewrite the
definitions of C M E X and J so we're all
clear on them. So C Recall counts all of
the comparisons between pairs of input
elements that [inaudible] whatever makes.
Whereas an Xij only counts the number and
its going to be zero or one which compare
the ith smallest and the jth smallest
elements in particular. Now since every
comparison involves precisely one pair of
elements some I and some j, with I less
the j. We can write C as the sum of the
Xij's. So don't get intimidated by this
fancy double sum. All this is doing is
it's iterating over all of the ordered
pairs. So all of the pairs IJ, where I and
J are both between one and N, and where I
is strictly less than N. This double sum
is just a convenient way to do that
iteration. And, of course, no matter what
the pivots chosen are, we have this
equality, okay? The comparisons, are
somehow split up amongst the various pairs
of elements, the various I's and J's. Why
is it useful to express a complicated
random variable as a sum of simple random
variables? Well, because an equation like
this is now right in the wheelhouse of
linearity of expectation. So let's just go
ahead and apply that. Remember, and this
is super, super important, linearity of
expectation says that the expectation of a
sum. Equals, the sum, of the expectations,
and moreover, this is true, whether or not
the reign of variables are independent
?Kay and I'm not gonna prove it here, but
you might wanna think about the fact that
the X-I-J's are not in fact, independent.
They were using the fact that we need an
expectation towards, even for not
independent reign of variables. And why is
this interesting, well the left hand side.
This is complicated, right? This is the,
this is some crazy number of comparisons
by some algorithm on some arbitrarily long
array and it fluctuates between two pretty
far apart numbers and log in and then
squared. On the other hand, this does not
seem as intimidating, given X, I, J it's
just zero or one, whether or not these two
guys get compared or not. So that is the
power of this decomposition approach,
okay. So it reduces understanding of
complicated random variable to
understanding simple random variables. In
fact, because these are indicator random
variables, we can even clean up this
expression some more. So for any given
xij, being a 01 random variable, if we
expand the definition of expectation, just
as an average over the various values
it's, what is it. It's, well, it's some
probability it takes on the value zero,
that's possible. And there's some
possibility it takes on the value one. And
of course this zero part we can very
satisfyingly delete, cancel. And so the
expected value of a given XIJ is just the
probability that XIJ equals one. And
remember, it's an indicator random
variable. It's one precisely when the I
smallest and the J smallest, elements get
compared. So putting it all together. We
find that what we care about, the average
value of the number of comparisons made by
quick sort on this input array. Is this
double sum, which iterates over all
ordered pairs. Where each summand is the
probability that the corresponding x I j
equals one. That is the probability that z
I and z j get compared. And this is
essentially the stopping point for this
video, for the first part of the analysis.
So let's call this star and put a nice
circle around it. So whats gonna happen
next is that in the second video, for the
analysis, we're going to drill down on
this probability. Probability that a
given, pair of [inaudible] gets compared
and we're gonna nail it, we're gonna get
an exact expression as a function of I and
J, for exactly what this probability is.
Then in the third video we're going to
take that exact expression, plug it into
the sum, and then, evaluate this sum and
it turns out the sum will evaluate to the
[inaudible] and login. So that's the plan.
That's how you apply decomposition in
terms of 0-1 or indicator random
variables. Apply linearity of expectation.
In the next video we'll understand these
simple random variables, and then we'll
wrap up in the third video. Before we move
on to the next part of the analysis, I do
just want to emphasize that this
decomposition principle is relevant not
only for quicksort, but it's relevant for
the analysis of lots of randomized
algorithms. And we will see more
applications, at least one more
application later in the course. So just
to kinda really hammer the point home, let
me spell out the key steps for the general
decomposition principle. So first you need
to figure out what is it you care about?
So in Quick Sort we cared about the number
of comparisons, we had this lemma that
said the running time dominated our
comparisons so we understood what we
wanted to know - the average value for the
number of comparisons. The second step is
to express this random variable y as a sum
of simpler random variables. Ideally
indicator or 01 random variables. [sound]
Now you're in the wheel house of linearity
of expectation. You just apply it. And you
find that what it is you care about, the
average value. Of the random value, of the
random variable, Y. Is just the sum.
[sound] the probabilities of various
events. That, given XL random variable is
equal to one. And so the upshot is, to
understand this seemingly very complicated
left hand side, all you have to do is
understand something which, in many cases,
is much simpler. Which is, understand the
probability of these various events.
[sound]. In the next video, I'll show you
exactly how that's done in the case of
Quick Sort. Where these, where we care
about the XIJs, the probability that two
elements gets compared. So let's move on
and get exact expression for that