In this video I'll explain the
mathematical analysis of the randomized
linear time selection algorithm that we
studied in the previous video.
Specifically, I'm going to prove to you
the following guarantee for that
algorithm. For every single input array of
length n the running time of this
randomized selection algorithm on average
will be linear. Pretty amazing if you
think about it because that's barely more
what the time it takes just to read the
input. And in particular this linear time
algorithm is even faster than sorting.
So this shows that selection is a
fundamentally easier problem than sorting.
You don't need to reduce to sorting. You
can solve it directly in O(n) time.
I want to reiterate the same
points I made about quick sort. The
guarantee is the same. It is a general
purpose subroutine. We make no assumptions
about data. This theorem holds no matter
what the input array is. The expectation,
the average that's in the theorem
statement is only over the coin flips made
by the algorithm made inside it's code of our
own devising. Before we plunge into the
analysis, let me just make sure you
remember what the algorithm is. So it's
like quick sort. We partition around a
pivot except we only recurse once, not
twice. So we're given an array with some
length n. We're looking for the ith order
statistic, the ith smallest element. The
base case is obvious. You're not in the
base case; you choose a pivot p, uniformly
at random from the input array just like
we did in quick sort. We partition around
the pivot just like we did in pic, in
quick sort. That splits the array into a
first part of those elements less than the
pivot and the second part of those
elements which are bigger than the pivot.
Now, we have a couple of cases. The case
which is very unlikely so we don't really
worry about, if we're lucky enough to
guess the pivot as the ith order
statistic what we're looking for. That's
when the new position j. Of the pivot
element happens to equal I. What we're
looking for. Then, of course, we just
return it. That was exactly what we
wanted. In the general case, the pivot is
going to be in the position J, which is
either bigger than what we're looking for
I, that's when the pivot is too big or J.
It's position will be less than the ith order statistic
we're looking for. That's when the pivot
is too small. So if the pivot's too big,
if J is bigger than i  that when
we're looking for is on the left hand
side amongst the elements less than the
pivot. So that's where we recurse. We've
thrown out both the pivot and everything
to the right of it. That leaves us with an
array of J minus I elements and we're
still looking for the ith smallest among
these J minus1 smallest elements. And then
the final case, this is what we went
through in the quiz and last video, is if
we choose a pivot who's smaller than what
we're looking for, that's when J is less
than I, then it means we're safe to throw
out the pivot and everything less than it.
We're safe recursing on the second part of
those elements bigger than the pivot.
Having thrown out the J's smallest
elements, we're recursing on an element of
length of N-J and we're looking for the i-j
smallest element in those that
remain, having already thrown out the J
smallest from the input array. So that's
randomized selection. Let's discuss why
it's linear time on average. The first
thought that you might have, and this
would be a good thought, would be that we
should proceed exactly the same way that
we did in Quick Sort. You recall that when
we analyzed Quick Sort, we set up these
indicator random variables, x, i ,j
determining whether or not a given, pair
of elements got compared at any point in
the algorithm. And then we just realized
the sum of the comparisons is just the
sum, overall, of these x,i, js. We applied
linearity of expectation and it boiled
down to just figuring out the probability
that a given pair of elements gets
compared. You can analyze this randomized
selection algorithm in exactly the same
way. And it does give you a linear time
bound on average. But it's a little messy.
It winds up being not quite as clean as in the
quick sort analysis. Moreover, because of
the special structure of the selection
problem, we can proceed in an even more
slick way here than the way we did with
quick sort. So, again we'll have some
constituent random variables. We'll again
apply linearity of expectation but the
definition of those random variables is
going to be a little bit different than it
was in quick sort. So, first a preliminary
observation. Which is that the workhorse
for this randomized selection procedure is
exactly the same as it was in quick sort.
Namely it's the partition subroutine.
Essentially all of the work that gets done
outside of the recursive call just
partitions the input array around some pivot
element as we discussed in detail in a
separate video that takes linear time. So
usually when we say something's linear
time we just use big O notation. I'm gonna
go ahead and explicitly use a constant c
here for the operations outside the
recursive call. That'll make it clear that
I'm not hiding anything up my sleeves when
we do the rest of the analysis. Now what I
wanna do on this slide is introduce some
vocabulary, some notation which will allow
us to cleanly track the progress of this
recursive selection algorithm. And by
progress I mean. The length of the
array on which is currently operating.
Remember we're hoping for a big win over
quick sort, cuz here we only do one
recursive call, not two. We don't have to
recurse on both sides of the pivot just on
one of them. So it stands to reason, that
we can think about the argument making
more and more progress as a single
recursive calls operating on arrays of
smaller and smaller length. So the notion
that will be important for this proof is
that of a phase. This quantifies how much
progress we've made so far, with higher
numbered phases corresponding to more and
more progress. We'll say that the
r select algorithm at some midpoint of
its execution is in the middle of phase J.
If the array size that the current
recursive call is working on has length between
3/4th raised to the J times N and the
smaller number 3/4th J+1 times N. For example
think about the case where J equals zero.
That says phase zero recursive calls,
operate on arrays with size of N and 75
percent of N. So, certainly, the outermost
recursive call is going to be in phase
zero. Because the input array has size N.
And then, depending on the choice of the
pivot, you may or may not get out of phase
zero in the next recursive call. If you
choose a good pivot, and you wind up
recursing on something, that has, at most,
75 percent of the original elements, you
will no longer be in phase zero. If you
recurse on something that has more than 75
percent of what you started with, of the.
Input array, then you're still gonna be in
phase zero even in the second recursive
call. So overall the phase number J,
quantifies the number of times we've made
75 percent progress, relative to the
original input array. And the other piece
of notation that's going to be important
is what I'm going to call Xj. So for a
phase J, Xj simply counts the number of
recursive calls in which a randomized
selection algorithm is in phase J. So this
is gonna be some integer. It could be as
small as zero, if you think about it, for
some of the phases. Or it could be larger.
So why am I doing this? Why am I making
these definitions of phases and of these
XJs? What's the point? We're gonna
remember the point was we wanna be able to
cleanly talk about the progress that the
randomized selection algorithm makes
through its recursion, and what I wanna
now show you is that in terms of these
XJs, counting the number of iterations in
each phase, we can derive a relatively
simple upper bound on the number of
operations that our algorithm requires.
Specifically the running time of our
algorithm, can be bounded above by the
running time in a given phase, and then
summing those quantities over all of the
possible phases. So we're gonna start with
a big sum, over all the phases J. We want
to look at the number of recursive calls
that we have to endure in phase J, so
that's XJ by definition. And then we look
at the work that we do outside of the
recursive calls in each recursive call
during phase J. Now, in a given recursive
call, outside of its recursive call, we do
C times M operations where M is the length
of the input array and during phase J we
have an upper bound on the link of the
input array. By definition it's at most
three quarters raised to the J times N. So
that is, we multiply the running time
times this constant C this, we inherit
from the partition subroutine and then we
can, for the input length, we can put an
upper bound of three quarters raised to
the J times N. So just to review where all
of these terms come from, there's three
quarters J times N is an upper bound on
the array size. During phase J, this by
the definition of the phase. Then, if we
multiply that times c, that's the amount
of work that we do on each phase J
sub-problem. How much work do we do in
phase J overall or we just take the work per
sub problem that's what's circled in
yellow and we multiply it times the number
of such sub problems we have. And, of
course, we don't wanna forget any of our
sub problems so we just make sure we sum
all of our phases, j, to insure that at
every point we count the work done in each
of the sub problems. Okay? So, that's the
upshot of this slide. We can upper bound
the running time of our randomized
algorithm very simply in terms of phases
and the XJ's, the number of sub problems
that we have to endure during phase j. So,
this upper bound on our running time is
important enough to give it notation, we'll
call this star, this will be the starting
point of our final derivation when we
complete the proof of this theorem. Now
don't forget, we're analyzing a randomized
algorithm so therefore the left hand side
of this inequality the running time of r select,
that's a random variable. So
that's a different number depending on the
outcome of the random coin flips of the
algorithm. Depending on the random pick it
has chosen, you will get different random
running times. Similarly the right hand
side of this inequality. Is also a random
variable. That's because the X J's are
random variables. The number of sub
problems in phase j depends on which
pivots get chosen. So. To analyze, what we
care about is the expectations of these
quantities, their average values. So we're
gonna start modestly and as usual, this
will extend our modest accomplishments to
much more impressive ones using linearity
of expectation, but our first modest
goal is just to, to understand the
average value. Of an XJ, the expected
value of XJ. We're gonna do that in two
steps. On the next slide, I'm going to
argue that to analyze the expectation of
XJ, it's sufficient to understand the
expectation of a very simple coin flipping
experiment. Then, we'll analyze that coin
flipping experiment. Then we'll have the
dominos all set up in a row. And on the
final slide, we'll knock'em down and
finish the proof. So let's try to
understand the average number of recursive
calls we expect to see in a given phase.
So, again, just so we don't forget. Xj is
defined as the number of recursive calls
during phase J. Where a recursive call is
in phase J, if and only if the current sub
array length lies between three-fourths
raised to the J+1 times N. And then, the
larger number of three-fourths raised to
the J times N. So again, for example,
phase zero is just the recursive calls
under which the array length is between 75
percent of the original element and 100
percent of the original elements. So what
I wanna do next is point out that a very
simple sufficient condition guarantees
that we'll proceed from a given phase onto
the next phase. So it's a condition
guaranteeing termination of the current
phase. And it's an event that we've
discussed in previous videos. Mainly that
the pivot that we choose gives a
reasonably balanced split. 25-75 or
better. So recall how partitioning works,
we choose a pivot P. It winds up wherever
it winds up. And the stuff to the left of
it's less than P. The stuff to the right
of it is bigger than P. So 25 to 75 split
or better, what I mean is that each of
these, each, the first part and the second
part has, at most, 75 percent of the
elements in the input array. Both have
twen-, both have at least 25%, and, at
most, 65%. And the key point is, that if
we wind up choosing a pivot that gives us
a split that's at least as good the
current phase must end. Why must the
current phase end? Well, to get a 25, 75
split or better than no matter which case
we wind up in, in the algorithm we're
guaranteed to recurse on a sub problem that
has at most 75 percent of what we started
with. That guarantees that whatever phase
we're in now, we're going to be in an even
bigger phase when we recursed. Now, I want
you to remember something that we talked
about before, which is that you've got a
decent chance when you pick a random pivot
of getting something that gives you a 25,
75 split or better. In fact, the
probability is 50 percent. Right? If you
have an array that has the integers from
one to 100 inclusive, anything from 76 to
s, 26 to 75 will do the trick. That'll
insure that at least the first 25 elements
are excluded from the rightmost call and
at least rightmost 25 elements are
excluded from the left recursive call. So
this is why we can reduce our analysis of
the number of recursive calls during a
given phase, to a simple experiment
involving flipping coins. Specifically,
the expected number of recursive calls.
Now we are gonna see in a given phase J,
is no more than the expected number of
coin flips in the following experiment.
Okay, so you've got a fair coin, 50
percent heads, 50 percent tails. You
commit to flipping it until you see the
head and the question is, how many coin
flips does it take up to and including the
first head that you see? So the minimum
it's gonna be one coin flip if you hit a
head the first time it's one. If you get a
tails and then a head, then it's two. If
it's tails, tails, head it's three and so
on, and you always stop when you hit that
first head. So what's the correspondence?
Well, think of heads as being you're in
Phase J, and if you get a good pivot, it
gives you a 25/75 split. Call that heads.
And it guarantees that you exit this Phase
J. Just like it guarantees that you get to
terminate the coin flipping experience,
experiment. Now, if you get a pivot which
doesn't give you a 25/75 split, you may or
may not pass to a higher Phase J, but in
the worst case, you don't. You stick to
phase J is you get a bad split, and that's
like getting a tails in the coin flipping
experiment, and you have to try again.
This correspondence give us a very
elementary way to think about the progress
that, that our randomized selection
algorithm is making. So, there's one
recursive call in every step in our
algorithm, and each time we either choose
a good pivot or a bad pivot, both could
happen, 50-50 probability. A good pivot
means we get a 75-25 split or better. A
bad pivot means, by definition, we get a
split worse than 25-75. So what have we
accomplished? We've reduced the task of
upper bounding the expected number of
recursive calls in a phase J to
understanding the expected number of times
you have to flip a fair coin before you
get one hit. So on the next slide we'll
give you the classical and precise answer
to this coin flipping experiment. So, let
me use capital N to denote the random
variable, which we were just talking
about, the number of coin flips you need
to do before you see the first heads. And,
it's not very important, but you should
know that these random variables have
their own name. This would be a geometric
random variable with parameter one-half.
So you can use a few different methods to
compute the expected value of a geometric
random variable such as this, and brute
force using the definition of expectation
works fine as long as you know how to
manipulate infinite sums. But for the sake
of variety, let me give you a very sneaky
proof of what it's expectation is. So the
sneaky approach is to write to the
expected value of this random variable in
terms of itself and then solve for the
unknown, solve for the expectation. So
let's think about it. So how many coins
flips do you need? Well for sure you're
gonna need one. That's the best case
scenario. And now two things can happen,
either you get heads and that has 50
percent probability you stop or you get
tails that happens with 50 percent
probability and now you start all over
again. Again you just put points until you
get first heads. On average how many times
does that take. Well by the definition of
capital N you expect. The expectation of N
coin flips, in the case where you get
tails, and you have to start all over. So
this one represents the first coin flip,
the one-half is the probability that you
can't stop, that you have to start all
over probability of tails, and then
because it's a memory less process,
because when you start anew on the second
coin flip having gotten the tails, it's as
if you're back at time one all over again.
So now we have a trivial equation, in
terms of the unknown expected value of N
and the unique solution, the unique value,
that the expected value of capital N could
have, in light of this equation, is two.
So, on average if you flip a fair coin and
stop when you get heads, you're going to
see two coin flips on average. To make
sure you haven't sort of lost the forest
for the trees, let me remind you why we
were talking about this coin flipping
analysis in the first place. So recall in
the previous slide we showed that XJ, and
remember XJ is the number of recursive
calls you'd expect to see in a given phase
J, and we argued that the number of
recursive calls you're gonna see is bounded
above. By the expected number of coin
flips until the heads. So this exact
calculation of two for the coin flips
gives us an upper bound of two for the
number of recursive calls on average in
any given phase J. So now that we've got
all our ducks lined up in a row, let's
wrap up the proof on this final slide. So,
inherited from part one of the proof, we
have an upper bound. On the expected
running time. Of the R select algorithm.
This is what we were calling star on the
first brief slide In star, it looked a
little messy, but we had the sum over the
phases J. But we had two things that were
independent of j: the constant c and the
original input length n, so let me just
yank the c and the n out front. And then
we have this residual sum over the phases
J. Of three quarters raised to the J
remember that comes from our upper bound
on the sub problem size during phase J and
then of course we have to keep track of
how many phase J sub problems we have
solved that by definition is XJ. Now star
was written as a rand in accordance terms
to the random variables. Now we're gonna
go ahead and take the expectations and
again I have said this over and over but
don't forget where's the expectation come
from. This is over the random pivot
choices that our code makes. So the
expected running time of the algorithm
is most the expectation of this start
quantity. So like I said earlier, pretty
much every time we're gonna do any
analysis of [inaudible] process, we're
gonna wind up using linearity of
expectation at some point. Here is where
we do it. Linear expectation says the
expectation of a sum is just the sum of
the expectations. So we yank the c and the
n outside of the expectation. We yank this
sum over phases. Outside of the
expectation. We yank this three-fourths
raised to the J outside of the expectation
and then we just have the expected value
of XJ, the average number of recursive
calls we expect to see in HJ. Now on the
previous two slides, we figured out an
upper bound on how many recursive calls we
expect to see in each phase. So first by
the coin flip analysis, by the reduction
of the coin flip analysis, this is the
most expected number of coin flips N,
which on the previous slide, we argued was
exactly two. So bringing that two out in
front of the sum, that no longer depends
on J. So we get a most 2CN. Times the sum
over phases J, of three quarters raised to
the J. Now this kind of sum we have seen
previously in the course. It came up when
we were analyzing the master method and we
summed up our running time upper bounds
over the levels of our recursin tree.
And if we're not in case one if we're in
case two or three we had geometric sums
that were nontrivial. They require a
certain formula to calculate, so let me
remind you of that formula here, when the
three quarters are being powered up to the
J. So this has value at most, one over one
minus, the number that's getting powered,
so in this case it's three quarters, one
minus three quarters is a quarter check
reciprocal, you got four. And the upshot
is that the expected number of operations
that this randomized selection algorithm
uses to find the [inaudible] ordered
statistic in a given input array, is eight
times C times N. Where C is the, hidden
constant in the linear running time of
partition. And so that completes the
proof. The input array was arbitrary. We
showed the expected running time over the
random choices of the algorithm is linear
in N. That is, only a constant factor
larger than what is required to read the
input. Pretty amazing.