So the time has arrived for us to finish
the proof of the fact that this
deterministic algorithm based on the
median of median ideas, does indeed run in
linear time. We've done really all the
[inaudible] difficult work. We've
discussed the algorithmic ingenuity
required. To choose a pivot
deterministically that's guaranteed to be
pretty good. So remember the idea was you
take the input array, you logically break
it into groups of five, you sort each
group. That's like the first round of a
two round knockout tournament. The winners
of the first round are the middle elements
of each group of five. That's the initial
set of medians. And then the second around
we take a median of these N over five
first round winners, and that's what we
return as the pivot. And we proved this
key lemma which is the 30/70 lemma, which
says that if you choose the pivot by this
two round knockout tournament, you're
guaranteed to get a 30/70 split or better.
So your recursive call in line six or
seven. Of having a de-select is guaranteed
to be on an array that has at most 70
percent of the elements that you started
with. In other words you're guaranteed to
prune at least 30 percent of the array
before you recurs again. But what remains
to understand is whether or not we've done
a sensible trade off. Have we kept the
work required to compute this 30/70 split
small enough. That we get the desired
linear running time. Or have we, is the
cost of finding a pretty good pivot
outweighing the benefit of having
guaranteed good splits? That's what we
gotta prove. That's the next subject.
Here's the story so far. You'll recall
that, as usual, we define T of N to be the
worst case running time of an algorithm.
In this case, D select on inputs of array
length. I didn't put arrays of length N.
And we discussed, okay, there's the base
case as usual. But in the general case, we
discussed how, outside of the two
recursive calls. The deselect algorithm,
there's a linear number of operations.
What does it have to do? It has to do the
sorting, but each sorting is on a group of
sized constants, size five, so it takes
constant time for a group. There's a
linear number of groups, so step one takes
linear time, the copying takes linear
time, and the partitioning takes linear
time. So, there's some constant C, which
is gonna be bigger than one, but it's
gonna be constant. So, then outside of a
recursive cause. Deselect always does at
most C times N operations. Now what's up
with the recursive calls. Well, remember
there's two of them. First, there's one on
line three that's just responsible for
helping choose the pivot. This one we
understand. It's always on twenty percent
of the imputed rate of like the first
round winners, so we can very safely write
T of N over five for the work done, in the
worst case, by that first recursive call.
What we didn't understand until we proved
the key lemma was what's up with the
second recursive call, which happens on
either line six or line seven. The size of
the imputed rate on which we recursed
depends on the quality of the pivot, and
it was only when we proved the key lemma
that we had a guarantee on the.
[inaudible] 30-70 split or better what
does that mean? That means the largest
sub-array we could possibly recurs on has
seven-tenths N elements. So what remains
is to find the solution for this
recurrence and hopefully prove that it is
indeed big O event. So I'm going to go
ahead and rewrite the occurrence at the to
of the slide. We're not really going to
worry about the T to one equal one. What
we're interested in is the fact that the
running time on an input of length N is at
most C times N. Where again c is some
constant which is gonna have to be at
least one, given all the work that we do
outside of the recursive calls. Plus the
recursive call on line three on an array
of size n over five. Plus the second
recursive call, which is on some array
that has size in the worst case
seven-tenths n. So that's cool. This is
exactly how we handle the over
deterministic divide and conquer
algorithms that we studied in earlier
videos. We just wrote down a recurrence
and then we solve the recurrence, but now,
here's the trick. And all of the other
recurrences that came up. For example,
Merge Short, Strassner's Matrix
Multiplication Algorithm, [inaudible]
multiplication, you name it. We just plug
the parameters into the masters method.
And because of the power of the master
method, boom! Out popped up an answer. It
just told us what the recurrence evaluated
to. Now, the master method, as powerful as
it is, it did have an assumption, you
might recall. The assumption was that
every sub-problem solved had the same
size. And that assumption is violated by
this linear time selection algorithm.
There are two recursive calls. One of 'ems
on twenty percent of the original array.
The other one is probably on much more
than twenty percent of the original array.
It could be as much as 70 percent of the
original array. So because we have two
recursive calls, and sub problems of
different size, this does not fit into the
situations that the master method covers.
It's a very rare algorithm in that regard.
Now, there are more general versions of
the master method, of the master theorem
which can accommodate a wider class of
recurrences including this one here.
Alternatively we could push the recursion
tree proof so that we could get a solution
for this recurrence. Some of you might
want to try that at home. But I want to
highlight a different way you can solve
recurrences just for variety, just to give
you yet another tool. Now the good news of
the, about this approach that I'm gonna
show you is that it's very flexible. It
can be used to solve sort of arbitrarily
crazy recurrences. It's certainly going to
be powerful enough to evaluate this one.
The bad news is that it's very out of
hock. It's not very necessarily very easy
to use. It's kind of a dark art figuring
out how to apply it. So it's often just
guess and check, is what it's called. You
guess what the answer to the recurrence is
and then you verify it by induction. Here,
because we have such a specific target in
mind, the whole point of this exercise is
to prove a linear is not bound, I'm gonna
call it just hope and check. So we're
gonna hope there's linear of time and then
we're gonna try to produce a proof of that
just that verifies the linear time bound
using induction. Specifically what are we
hoping for, we're crossing our fingers
that there's a constant, I'm going to call
it A, A can be big but it's got to be
constant, and again remember constant
means it does not depend on N in any way.
Such that our recurrence at the top of
this slide T-N is bound above by A times N
for all and at least one. Why is this what
we're hoping? Well suppose this were true.
By definition T of N is a upper bound of
the running time of our algorithm. So it's
bound and [inaudible] by A times N then
it's obviously an O event. It's obviously
a linear time algorithm. It's obviously A
gets that gets suppressed in the big
rotation. So that's the hope, now let's
check it. And again, check mean just
verify by induction on N. So the precise
claim that I'm going to prove is the
following. I'm gonna go ahead and choose
the constant A. Remember all we need is
some constant A, no matter how big as long
as it's independent of N. That'll give us
the big O of N time. So I'm actually gonna
tell you what A I'm gonna use for
convenience. I'm gonna choose A to be 10C.
Now what is C? C is just a constant that
we inherit from the recurrence that we're
given. Now remember what this recurrence
means is this is what the running time is
of the deselect algorithm and the C times
N represents the work that's outside of
the recursive calls. So this is just a
constant multiple on the amount of linear
work that deselect does for sorting the
groups, for doing the partitioning and for
doing the copying. And so there's gonna be
some small task at a reasonable cost and,
and for the proof I'm just gonna multiply
that by ten and use that as my A. And the
claim is if I define A in that way then
indeed, it is true that for all and at
least one, T of N is banded above by A
times N. Now, I realized I just, I pulled
this constant A out of nowhere, right? Y10
times C. Well, if you recall our
discussion when we proved that things were
big O of something else, there again,
there was some constant. So to formally
prove that something is big O of something
else, you have to say what the constant
is. And in the proof, you always wonder
how do you know what constant to use? So,
in practice, when you're actually, if you
have to actually do one of these proofs
yourself, you reverse engineer what kind
of constant would work. So you just go
through the argument with a generic
constant. And then you're like, oh, well,
if I set the constant to be this, I can
complete the proof. So we'll see, that's
exactly what's gonna happen in the proof
of this claim. It'll be obvious. The very
last line you'll see why it shows A equals
10C. So I just reverse engineered what I
needed for the proof. But to keep the
proof easy to follow line by line I
decided to just full disclosure tell you
the cost right at the beginning. Now no
prizes for guessing that the way this
proof proceeds is by induction on N.
Induction's the obvious thing to use,
we're trying to prove an assertion for
every single positive number N and
moreover we're given this recurrence which
relates solutions of smaller sub-problems
to that of bigger problems. So that sets
things up for use of the inductive
hypothesis. If you want a longer review of
what proofs by induction are, I suggest
that you go back and re-watch the optional
video where we prove the correctness of
quicksort. That is, is a fairly formal
discussion of what the template is like
for a proof by induction. And that's the
one we're gonna apply here. So, there's
two ingredients in any proof by induction
is, is a usually trivial one in the form
of a base case. That's also gonna be
trivial here. In the base case you just
directly establish the assertion when n
equals one. So, we're trying to prove that
t of n is the most a times n for every n
when n equals one we could just
substitute. But what we're trying to prove
is that t of one is at most a time one
also known as a. And we're given that t of
one is one. Right that's the base case of
the recurrence that we're given. So that's
what we're using here. What we want to be
true is that this isn't the most a times
one, but it is. So the constant c we're
assuming is at least one, so it certainly
can multiply c times ten to get a. It's
definitely at least one. So the right hand
side here is unquestionably bigger than
the left hand side. A in fact is bigger
than ten, let alone bigger than ten. So
the interesting ingredient is generally
the inductive step so remember what you do
is here is you assume you've already
proven the assertion that, in this case
the T of N is at most AN for all smaller
integers, and now you just merely have to
prove it again for the current integer. So
we're now interested in the case where N
is bigger than one and the assumption that
we've already [sound] proven to everything
smaller is called inductive hypotheses. So
what does it mean that we already proved
it for all smaller numbers, that means we
can use in the proof of our inductive step
the fact that P of K is the most a times K
for all K strictly less than N. All we
gotta do is enlarge the range of N's to
which this holds to one more to the
current value N. And all we have to do is
follow our nose. So pretty much, we, we
have to start on the left hand side with T
of N, and we have to wind up on the right
hand side with A times N. And pretty much,
at every step of the proof, there's just
gonna be one conceivable thing we could
do. So we just follow our nose. We start
with what we wanna upper bound, T of N.
Well, what do we got going for us? The
only thing we can do at this point is
invoke the recurrence that we were given
up here. So we have an upper bound on T of
N in terms of the T value of smaller
integers. So we are given that T of N is
at most C times N, plus T of N over five,
plus T of seven-tenths N. Of course
ignoring fractions, you would round up or
round down, if you wanted to be precise,
and the auxiliary lecture notes are more
precise, if you want to see what the gory
details look like. But it's really just
exactly the same argument. One just has to
be a little bit more anal about it. So now
that we've invoked the recurrence, what
can we possibly do, right? We can't really
do any direct manipulation on any of these
three terms. But fortunately, we have this
inductive hypothesis. That applies to any
value, any integer which is less than N.
So we have her, N/5, that's certainly less
than N. We have 70 percent of N. That's
certainly less than N. So we can apply the
inductive hypothesis twice. We already
know that these T values are bounded above
by A times their arguments. So T of N over
5's at most A, times N over five. T of
seven-tenths N is at most A, times
seven-tenths N. Now we can group terms
together, not we're comparing apples to
apples. So we have N, times quantity C,
plus A/5, plus seven-tenths A. Let me just
go ahead and group the two A turns
together. And that's gonna be nine-tenths
A. No, don't forget where we're going,
what the end goal is. We want a upper
bound T of N by AN. So we wanna write that
this is bounded above by A times N. And
now you see exactly how I reverse
engineered our choice of A, as a function
of the given constant C. Since A is ten
times as big as C, if I take 90 percent of
A and add C, I just get A back. So by our
choice of A. This equals AN. And that
pretty much wraps things up. So don't
forget what all this stuff stands for. So
what did we just prove? What did we just
prove by induction? We proved T of N is,
at most, a constant times N for every N.
That is, T of N is Big O of N. What was T
of N? That was the running time of our
algorithm. That's all we cared about. So
because T of N is Big O of N, indeed,
deselect runs in O of N time.