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.