Now let's turn to the analysis of the deterministic selection algorithm that we
discussed in the last slide by Blum, Floyd, Pratt, Rivest, and Tarjan. In
particular, let's prove that it runs in linear time on every possible input.
Let's, remind you what the algorithm is. So the idea is, we just take the R select
algorithm. But instead of choosing a pivot at random, we do quite a bit more work to
choose what we hope is going to be a guaranteed pretty good pivot. So again,
lines one through three are the new choose pivot subroutine. And it's essentially
implementing a two round knockout tournament. So first, we do the first
round matches. So what does that mean? That means we take A we think of it as
comprising these groups of five elements. So the first five elements one through
five and the elements six through ten and points eleven through fifteen and there
again and so on. If we sort each of those five using, let's say, merge sort although
it doesn't matter much, then the winner in each of these five first round matches is
the median of those five. That is the third highest element, third largest
element out of the five. So we take those in over five first round winners the
middle element of each of the five and the sorted groups, we copy those over into a
new array of capital [inaudible] and [inaudible] in it for five. And then we.
Second round of our tournament at which we elect the medium of these N over five,
first round winners as our final pivot, as our final winner. So, we do that by
recursively calling deselect on C. It has a length N over five [inaudible] for the
medium. So that's the N over tenth [inaudible] statistic in that array. So,
we call the pivot P and then we just proceed exactly like we did. And in the
randomized case. That is, we partition A around the pivot, we get a first part, a
second part, and we recurs on the left side or the right side as appropriate,
depending on whether the pivot is less than or bigger than the element that we're
looking for. So the claim is, believe it or not, that this algorithm runs in linear
time. Now, you'd be right to be a little skeptical of that claim. Certainly, you
should be demanding from me some kind of mathematical argument about this linear
time claim. It's not at all clear that that's true. One reason for skepticism is
that this is an unusually extravagant algorithm. In two senses for something
that's gotta run in linear time. First is, first is it's extravagant use of
recursion. There are two different recursive calls, as discussed in the
previous video. We have not yet seen any algorithm that makes two recursive calls
and runs in linear time. The best case scenario was always [inaudible] for our
two recursive call algorithms like merge sort or quick sort. The second reason is
that, outside the recursive calls, it seems like it?s just kind of a lot of
work, as well. So, to drill down on that point, and get a better understanding for
how much work this algorithm is doing, the next quiz asks you to focus just on line
one. So when we sort groups of five in the input array how long does that take. So
the correct answer to this quiz is the third answer. Maybe you would have guessed
that given that I'm claiming that the whole algorithm takes linear time, you
could have guessed that this sub-routine is going to be worse than linear time. But
you should also be wondering you know, isn't sorting always N log N so, aren't we
doing sorting here. Why isn't the N log N thing kicking in? The reason is we're
doing something much, much more modest than sorting the linked N input array, all
we're sorting are these puny little sub-arrays that have only five elements
and that's just not that hard, that can be done in constant time so let me be a
little more precise about it. The claim is that sorting an element, an array with
five elements takes only some constant number of operations. Let's say 120. Where
did this number, 120 come from? Well, you know, for example, suppose we used merge
sort. If you go back to those very early lectures, we actually counted up the
number of operations that merge sort needs to sort an array length of M. For some
generic M, here M is five, so we can just plug five into our previous formula that
we computed from merge sort. Right if we plug amicle five into this formula, what
do we get, we get six times five times log base 205+1. Who knows what log base 205
is, that's some weird member but it's gonna be a most three right. So that's the
most three of three+1 is four multiply that by five and again time six and will
get you 120. So it's constant time to sort just one of these groups of five. Now of
course, we have to do a bunch of groups of five because there's only a linear number
of groups. Constant for each, so it's gonna be linear time overall. So to be
really pedantic. We do 120 operations at most per group. There's N over five
different groups. We multiply those, we get 24 N operations. So do all the sorting
and that's obviously a big O event. So linear time for step one. So having warmed
up with step one. Let's look now at the whole seven line algorithm, and see what's
going on. Now I hope you haven't forgotten the paradigm that we discussed for
analyzing the running time of deterministic divide and conquer
algorithms like this one. So namely we're gonna develop a recurrence and remember a
recurrence expresses the running time, the number of operations performed, in two
parts. First of all, there's the work done by the recursive calls on smaller
sub-problems. And secondly, there's the work done locally, not in the recursive
calls. So let's just go through these lines one at a time, and just do a running
tally of how much work is done by this algorithm, both locally and by the
recursive calls. So the quiz was about, step number one. We just argued that since
it's constant time to sort each group, and there's a linear number of groups, we're
gonna do linear work, theta of N. For step one. So copying these first round winners
over in to their special array C is obviously linear time. Now, when we get to
the third line, we have a recursive call, but it's a quite easy recursive call to
understand. It's just, recursing on a, a ray that has size twenty percent as large
as the one we started with, on the N over five elements. So this, remember the
notation we used for recurrences. Generally, we denote by capital T the
running time of an algorithm on [inaudible] of a given length. So this is
going to be the running time that our algorithm has in the worst case on inputs
of length N over five. Cuz N over five is the length of the array that we're passing
to this recursive call. Good. Step four, partition. Well we had. Videos about how
they were going to partition the Y to linear time. We knew that all the way back
from quick sort, so that's definitely Theta of N. Step five is constant time,
I'm not going to worry about it. And finally we get to lines six and seven so
at most one of these will execute so in either case there's one recursive call. So
that's fine, we know in recurrences when there's recursive call we'll just write
capital T of whatever the input length is. So we just have to figure out what the
input length here is. It was N over five in step, in line three so we just have to
figure out what it is in line six or seven. Oh yeah, now we're remembering why
we didn't use recurrences when we discussed randomized quick sort and. The
randomized selection algorithm. It's because we don't actually know how big the
recursive call is, how big the input passed to this recursive call in line six
or seven is. Line three, no problem. It's guaranteed to be twenty percent of the
input array cuz that's how we defined it. But for line six or seven, the size of the
input array that gets passed to the, to the recursive call depends on how good the
pivot is. It depends on the splitting of the array A into two parts, which depends
on the choice of the pivot P. So at the moment all we can write is T. Of question
mark. We don't know. We don't know how much work gets done in that recursion,
cause we don't know what the input size is. Let me summarize the results of this
discussion. So write down a recurrence for the D select algorithms. So with T of N
denote the maximum number of operations the D select ever requires to terminate an
array of input [inaudible]. It's just the usual definition of T of N when using
recurrences. What we established in our tally on the last slide is that deselects
does linear stuff outside the recursive calls. It does the sorting of groups of
five. It does the copying, and it does the partitioning. Each of those is linear, so
all of them together is also linear. And then it does two recursive calls. One
whose size we understand, one whose size we don't understand. So, for once I'm not
going to be sloppy and I'm going to write out an explicit constant about the work
done outside of the recursive cause. I'm going to write [inaudible], I'm going to
actually write C times N for some constant C. So of course no one ever cares about
base cases, but for completing this let me write it down anyways. When D select gets
an input of only one element it returns it, what's called that one operation for
simplicity. And then in the generals cases and this is what's interesting. When
you're not in the base case and you have to recurs, what happens? Well you do a
linear work outside of the recursive call. So that's C times N for some constant C. C
is just the [inaudible] constant on all of our big thetas on the previous slide. Plus
the recursive call in line three, and we know that happens on an array of size
[inaudible] five. As usual, I'm not gonna worry about rounding up or rounding down,
it doesn't matter. Plus our mystery recursive call on an array of unknown
size. So that's where we stand and we seem stuck because of this pesky question-mark.
So, let's prove lemma which is gonna replace this question-mark with something
we can reason with, with an actual number that we can then analyze. So the upshot of
this key lemma is that all of our hard work in our choose pivot subroutine in
lines one through three bears fruit in the sense that we're guaranteed to have a
pretty good pivot. It may not be the median, it may not give us a 50/50 split.
Then we could replace the question mark with, one-half times N. But it's gonna let
us replace the question mark by seven-tenths times N. Now, I don't wanna
lie to you, I'm gonna be honest, it's not quite 7/10N, it's more like 7/10N minus
five, there's a little bit of additive error, so, taking care of the additive
error adds nothing to your conceptual understanding of this algorithm or why it
works. For those of you who want a truly rigorous proof, there are some posted
lecture notes which go through all the gory details. But in lecture I'm just
gonna tell you what's sort of morally true and ignore the fact that we're gonna be
off by three here and four there. And then we'll be clear when I show you the proof
of this limit, where I'm being a little bit sloppy and why it really shouldn't
matter, and it doesn't. So to explain why this key limit is true why we get a 30 70
split or better guaranteed, let me set up a little notation. I'm getting sick of
writing N over five over and over again, so let's just give that a synonym, let's
say, K. So this is the number of different sort of first round matches that we have,
the number of groups. I also want some notation to talk about the first round
winners, that is the medians of these groups of five, the K first round winners.
So, were gonna call XI the [inaudible] smallest of those who win their first
round match and make it to the second round. So just to make sure the notation
is clear, we can express the pivot element in terms of these X?s. Remember, the pivot
is the final winner. It wins not only its first round tournament, but it also the
second round tournament. It's not only the middle element of the first group of five.
It's actually the median of the N over five middle element. It's the median of
the medians. That is, of the K middle elements, it's the K over two order
statistic, [inaudible] K over two smallest. I'm saying this, assuming that K
is even. If K was odd, it would be some slightly different formula as you know. So
let's remember what we're trying to prove. We're trying to prove that for our
proposed pivot, which is exactly this element X sub K over two, it's exactly the
winner of this 2-round knockout tournament. We're trying to argue that for
this proposed pivot, we definitely get a 30-70 split or better. So what that means
is, there better be at least 30 percent of the elements that are bigger than the
pivot. That way if you recurs on the left side on the first part, we don't have to
deal with more that more than 70 percent of the original elements. Similarly, there
better be at least 30 percent of the elements that are smaller than the pivot.
That way if we recurs on the right hand side we know we don't have to deal with
more than 70 percent of the original input elements. So if we achieve this goal, we
prove that there's at least 30 percent on each side of XK over two, then we're done.
That proves the key lemma that would get a 30/70 split or better. So I'm gonna show
you why this goal is true. I'm gonna introduce a thought experiment. And I'm
gonna lay out it abstractly. Then we'll sorta do an example to make it more clear.
And then we'll go back to the general discussion and finish the proof. So what
we're gonna do is a thought experiment, for the purposes of counting how many
elements of the input array are bigger than our pivot choice, and how many are
smaller. So in our minds we're going to imagine that we're taking elements in A
and rearrange them in a 2D grid. So here are the semantics of this grid. Each
column will have exactly five elements that will correspond to one of the groups
of five. So we'll have N over five columns corresponding to our N over five groups in
our first round of our tournament. [inaudible] is not a multiple of five then
one of these groups has size between one and four but I'm just not gonna worry
about it, that some of the additive loss, which I'm ignoring. Moreover were going to
arrange each column in a certain way so that going from bottom to top the entries
of that go from smallest to largest. So this means that in this grid we have five
rows. And the middle row, the third row, corresponds exactly to the middle
elements, to the winners of the first round matches. So because these middle
elements these first round winners are treated specially, I'm going to denote
them with big squares, the other four elements of the group two of which are
smaller two of which are bigger are just going to be little circles. Furthermore,
in this thought experiment, in our mind, we're going to arrange the columns from
left to right in order of increasing value of the middle element. Now remember, I
introduced this notation X of I is the [inaudible] smallest amongst the middle
elements. So a different way of what I'm trying to say is that the leftmost column
is the group that has X1 as its middle element. So among the N over five middle
elements, one of the groups has the smallest middle elements. We put that all
the way on the left. So this is gonna be X1 in the first column, the smallest of
the first round winners. X2 is the second smallest of the first round winners, X3 is
the third smallest and so on. At some point we get to the median of the first
round winners, XK over two. And then, way at the rights is the largest of the first
round winners. And I'm sure that you remember that the median of medians which
is XK over two is exactly our pivot. So this is our lucky winner. I know this is a
lot to absorb, so I'm gonna go ahead and go through an example. If what I've said
so far makes perfect sense, you should feel free to skip the following example.
But if there's still some details you're wondering about, and hoping this example
will make everything crystal clear. So let's suppose we have an input array. I
need a, a slightly big one to [inaudible] grid make sense. Let's say there's an
input array of twenty elements. So there's going to be the input array, which is in a
totally arbitrary order. There's gonna be the vertical [inaudible] after we sort
each group of five. And then I'm gonna show you the grid. So this is the input
we're all gonna use. Let's now go ahead and delineate the various groups of five.
So after sorting this group, you get the following. From each group there's a
single winner mainly the middle element so that would be the twelve, and the six, and
the nine, and the fourteen, those are the four survivors from the first round of the
tournament. And the median of these four elements which, at the end of the day is
gonna to be our pivot is the second smallest of the four, that's how we define
the median from an even number of elements, so that's gonna be the nine. So,
this first transformation from the input array, to this vaguely mini sorted version
of the input array with the groups of five sorted, this we actually do in the code.
This happens in the algorithm. Now, this grid we're just doing in our minds. Okay?
We're just in the middle of proving why the algorithm is fast. Why the fit bits
guaranteed to give us close to a, a 30 70 split or better. So, let me show you an
example of this grid in our mind, what it looks like for this particular input. So
the grid always has five rows. The columns always have five elements cause the
columns correspond to the groups. Here because N equals twenty and over five is
four. So there's gonna be, four columns and five rows. And moreover we arrange the
columns from left to right so that these middle elements go from smallest, to
largest. So the middle elements are six nine twelve and fourteen and we're gonna
draw the columns in that order from left to right. So first we'll write down the
middle elements, the middle row from decreasing to increasing, six, nine,
twelve, fourteen. Again the median of this is our pivot, which is the nine. And then
each column is just the other four elements that goes along with this middle
element from decreasing to increasing as we go from bottom to top. So this is the
grid that we're been talking about on the other slide, in this particular example.
So I hope that makes what we're talking about clear, what these X?s mean, and what
worry we have amongst the rows, amongst the columns and so on. So let?s go back to
the general argument. Here is the key point, here is why were doing this entire
thought experiment, it?s going to let us prove our key limit. We're going to get a
30/70 split or better. 30 percent of the stuff at least is less than the pivot; 30
percent at least is bigger than the pivot. So why is there at least 30 percent of the
stuff below the pivot? Why is the pivot bigger then at least 30%? Well, it's
bigger then everything to the left and everything below the stuff to the left.
That is we know that XK over two is bigger than the K over two minus one elements.
That is to the left of it, those other middle elements that it's bigger then.
That's because it's the median of the medians. >> So, if we just go straight
west from the pivot we only see stuff which is less. Furthermore, these columns
are arranged from decreasing to increasing order as we go from south to north, from
bottom to top. So if you travel south from any of these smaller XMI we only see stuff
which is still smaller. So all we're using in here is transitivity of the less than
relation. If you go straight west you see stuff which is only smaller from any of
those points if you go southward you'll see stuff which is even smaller than that.
So this entire yellow region, everything southwest of the pivot element, is smaller
than it. And that's a good chunk of the grid. Right? So for all of these columns,
it's basically three out of the five, or 60 percent of them are smaller than the
pivot, and half of the columns, essentially, are in this part of the grid.
So if the pivots bigger than 60 percent of the stuff in 50 percent of the groups that
means it's bigger than 30 percent of the elements overall. And if we reason in an
exactly symmetric way, we find that the pivot is also smaller than at least 30
percent of the array. So to find things bigger than the pivot, what do we do?
First we travel eastward. That gives us middle elements that are only bigger than
it and then we stop wherever you want on our eastward journey and we head north,
and we're gonna see stuff which is still bigger. So this entire north eastern
corner. Is bigger than the pivot element, and again that's 50%, that's at 60 percent
of roughly 50 percent of the groups. Returning to our example, the southwest
region of the nine. Is this stuff, one, three, four, five, six. Certainly, all of
that is smaller than the nine. You'll notice there's other things smaller than
the nine as well. There's the eight, there's the two, there's the seven, which
we're not counting. But it depends on the exact array. Whether or not, in those
positions, you're gonna have stuff smaller than the pivot or not. So it's this yellow
region we're guaranteed to be smaller than the pivot. Similarly, everything northeast
of the pivot is bigger than it. Those are all double digit numbers and our pivot is
nine. Again there's some other stuff in other regions bigger than the pivot, the
twenty, the ten, the eleven, but again those are positions where we can't be
guaranteed that it will be bigger than the pivot. So it's the yellow regions that are
guaranteed to be bigger and smaller than the pivot, and that gives us the
guaranteed 30 70 split. Okay, so that proof was hard work, showing that this
deterministic choose pivot subroutine guarantees a 30-70 split or better. And
you probably feel a little exhausted and like we deserve a QED at this point. But
we haven't earned it. We have not at all proved that this deterministic selection
algorithm runs in linear time. Why doesn't a guaranteed 30-70 split guarantee us
linear time automatically? Well, we had to work pretty hard to figure out this
element guaranteeing this 30-70 split. In particular we had to invoke another
recursive call. So maybe this was a Pyrrhic victory. Maybe we had to work so
hard to compute the pivot that it outweighs the benefit we'd get from this
guarantee. 30 70 split. So, we still have to prove that's not the case even in
conjunction doing both of these things, we still have our linear time bound. We'll
finish the analysis in the next video. [sound].