OK.
So in this lecture today, we're going to be looking at a recurrence that's very similar to the one
we looked at in the previous lecture.
But we're going to look at a better way to solve it if we have something inside the recurrence called
floor division so we can go over kind of a new rule here today.
So let's revisit a somewhat familiar occurrence, which is the one we talked about in the last lecture
unless actually we had tea event over two plus one.
So this is similar, except it has these floor division operators around it.
So we talked a little bit about using floor division when we're doing our binary search.
But this time we have the actual floor revision present in our recursive call, part of the recursive
call, part of the recurrent solution here.
So this just means that we want to round down to the nearest integer just to remind you of that, that's
what floor division is.
And so you see our base case here as well.
But this kind of makes the recurrence interesting because the math doesn't work out as well as we'd
like for any value in.
So let's look at what we have to do here.
So the problem with this is that it gets a little weird when you think about whether occurrence would
make sense for all values of and if you're substituting, you know, in order to over and over, if
you're thinking about any possible value of in any point in time, it's a little weird with the Florida
vision mathematically.
So a better way to go about solving these recurrences with Florida vision is to use something called
the smoothness rule.
And so that's what we're going to talk about today.
So Smugglers Rule basically says that we can instead assume that N equals two to the K.
That gives us a nice just power of two and that that will give us a correct answer about the order of
growth for all values, events and this kind of like a really broad assumption to smooth this rule.
But people use it, so we introduce it here so it can help us with the currencies.
So, yeah, it just says that that will give us that correct answer for all of then when we're solving
our current situation.
So how do we use that?
So what we can do is actually just make an equal to two to the K.
So instead of us using in all the time, we're going to use two to the K instead.
And since we're doing that, we also need to change our base case here.
So our base case is T of one equals one.
And so since it's one in here, we need to put it in powers of two.
So what we're going to do is, say two to the zero, because two to the zero is one.
So this would be the same thing kind of T of quantity of two zero equals one.
So instead of thinking about doing our normal thing that we were doing like it, it ain't over to over
to to start out, we're instead going to think of this repetitive division as subtracting powers.
So from two to the K, so like two to the K minus one to start out instead of in over two or two.
So if you think about it, if you just do normal exponents like two to three or something like that,
just a positive number is basically a successive multiplication to get to that answer.
So if we want to do this represent the success of division, that's something that's actually more like
subtracting like an exponent.
So, you know, like negative exponents and stuff like that.
So only subtracting exponent.
We can better represent success of division.
And so that's kind of why the smoothness will use this concept right here.
So we're actually going to start out with that.
So let's get started in solving it here.
I'm just doing the same thing I did before, where in red we're just representing our original recurrence
for reference.
And what we're going to do to start out is just do what we said, we're going to substitute in with
two to the K, so if we do that, then we end up with something like this because instead of in over
two, over two, we're actually just going to start out with two to the K minus one.
So what we what we start out with, and I'm going to put this in yellow, because if you remember,
I'm going to kind of highlight all the yellow pieces of this, and that's what we're going to use later
on, define the term.
So that's what the yellow means as we're going through this recurrence.
It's going to eventually.
These are the pieces that we're going to use to find a pattern for the term.
So this is how we start out, you notice we're also doing that substitution here for the base case because
we need to put it in terms of two to the something.
So we're doing that to the zero.
And so let's start out just like we did in the last recurrence, we're going to say, OK, well, what
are we going to do for two to the K minus one?
So let's solve for that.
And when we do that for you two to the K minus one.
Instead of in when we have that over two, we can actually just say two to the K minus two so that we're
just kind of successfully keeps subtracting one each time we're doing another division by two.
You can think of it as you know, an additional, you know, at number here that we're subtracting.
So it came as long as two and so on and so forth.
So think about that repetitive division is now being represented in this manner.
So we end up with this answer for five, for two to the minus one.
So we have this tea of two to the K minus two plus one, and this was our substitution of two to the
K minus one into our original formula.
And then what we're going to do is substitute this whole thing where we left off, which was right here.
So now that we know to to the K minus one, we can substitute this to the K minus one with this whole
thing.
And that's what we're doing down here.
So you notice we put this whole, this whole, this whole thing right here in here.
And we have this extra plus one, so we're simplifying it just t- t- of two to the minus two plus two.
So let's continue on just like we did in the previous slide show.
So this is where we left off.
And now we're going to say, hey, what about T of to the Caymans to.
Well, what is that?
That's actually two to the K minus three plus one here.
So now what we can do after substituting this in the original equation.
We're actually we're just so sorry, we're solving this, so what we want to do after this is now a
substitute, our answer for to the K minus to in the original equation.
So this whole thing is getting substituted here.
For this.
So we had this extra plus two, and now we added this with the plus one, and so if we simplify it,
it's actually going to be two to two to the Chemo's three plus three.
So this was our substitution back into the place that we left off.
All right, cool.
And yeah, when I was saying stuff to you, this in the original equation that that is yes, actually
what I meant.
So you're substituting this for in.
So that's why we ended up with this.
So we seem to have that plus one there.
And if we do two to the K minus two or two in here, it's to the K minus three.
So let's continue on.
This is where we left off.
And now we're going to say, hey, let's find two minus three.
So to the minus three or two to the minus four.
So we're having that plus the one, we get this whole thing.
Let's take this whole thing.
Subs two for two to the K K minus three.
So we do that and we have it in here.
And now we have this three so simple that we have two that came out as four plus four.
OK, so we've gone a few times now.
Let's see if we can find a pattern.
So you notice here I put all of the yellow.
Portions that were highlighted here before, so.
All those who are putting them back to back here to see if we can find a pattern.
So let's see if Toyota came minus one plus one due to the came with two plus two to two to the K minus
three plus three and two to the K minus four plus four.
So you know, these obviously you can probably see a pattern is very similar to what we talked about
before.
We have similar numbers here.
They kind of correspond with which I which iteration we are at.
You know, so this was kind of the first one and then the second one and the third one and the fourth
one.
So what we can actually say is the eighth term is going to be T of two to the K minus I plus I.
Because it corresponds with the term, we're on the one to first term, second term, third or fourth
term.
So what we can say then is that those eyes match up with these numbers here and so they can be replaced
with I.
OK, so let's solve the rest.
So here's our term.
So we're going to do what we did before.
Let's assume that the base case let's assume the base case T of one where the base case.
So then what we can do is do the same thing we did before where we take what's inside of the parentheses
of the T here and we set it equal to what's inside here, which is one.
So we're doing to the case when I say equals one.
And you notice that I've kind of like got this in terms of, I guess, basically what we want to do
is find out what I is.
So we can replace it in the equation.
And then after that, we'll try and get back to having it in terms of end so we can actually settle
for an answer just like we did in the previous lecture.
So I'm doing that here, and there's actually a slightly easier way I noticed I did this and kind of
like.
You know, like an extra.
Steps kind of way.
I guess that's why we've put it like that, but when I really could have just looked at the fact, you
know, you can look at like it being two to the zero.
So.
I'll explain that in a second, but basically what you also could have done here instead of this mess
is just say, OK, well, we know that T of one is actually T of two to the zero.
And then if we said two to the zero equal to two to the K minus I is basically saying K minus II equals
zero.
And then we could have arrived at the same result.
And that's probably a simpler way to do it.
But we can also do here is just follow the traditional rulers of exponents and such.
And so.
What you can say for this term can be simplified actually into something that has this subtraction up
here in the exponent, you can actually say it's two to the K over two to the eye.
So if you do that, then what you can do is you have two to the K over to to the right here.
So what you can what we did to get to this step was we multiplied by two to the I to remove this denominator
on this fraction here.
And so we also have to multiply by two over here if we do that.
So we got rid of this.
And then we multiplied one times, anything is just that thing, so we ended up with after getting rid
of this, we have two to the K equals two to the I over on this side.
And then some were just tuned this something equals two to the something we can actually just say that
K equals I.
So this is another way to do that.
But of course, you could have just done that.
Two to the zero is equal to two to the K minus I.
And then you could say that.
You know, K minus II is equal to zero, and then you could have added I to both sides, and that would
have made the same result k equals I.
So same thing there that would probably be a better way to do it.
So I want to point that out.
So now we have this K equals I, so that's the same thing as saying I equals K, so now that we know
equals K, we can actually substitute K for I in this I term to simplify it.
So therefore, we replace it with Kay, so we actually end up just getting tee of two to the K minus
K plus K.
K minus K, something minus itself is zero.
And so we get T of two to the zero plus K.
Huh.
Interesting.
T of two to the zero.
Well, what is that due to the zero?
Well, that's one, right?
So that's T of one, and we already know what Tier one is.
So basically.
What we can do is simplify this, so to to this zero is one.
So we know that this is actually T of one and we know T of one equals one for our base case, if you
recall that.
At the same time, what we're going to do is recall that N equals two to the K.
And we also want to recall the properties of logarithms that we discussed, this can actually be reorganized
in terms of a logarithm.
So if you remember back to what we talked about with large, see if you can actually maybe pause the
video and turn this into an expression with a logarithm.
OK, so what we would actually do is we can rearrange n equals two to the K to actually be K equals
log base two of N.
And then, like I said before, recall that T of two to the zero is actually T of one because two of
the zero is one.
So the same thing as saying T one, and we know that T of one equals one.
Knowing all these things, we can actually change this expression right here.
So if K goes a long way to heaven, we can substitute for K and if we know T of two, the zero is T
of one and that T of one equals one, we can actually substitute that right here.
And so what we end up with is we can say that we actually have something like T in so we can get this
back.
In terms of N, since we have this log base, two women equals one plus log base, two of RN.
And our time complexity would then be theta log in because we can get rid of this constant and ignore
the base to.
And so that's fully simplified now, and we have solved it all the way to get tight bounds.
OK, so hopefully that makes sense.
This part, there was kind of a lot going on, but if you just kind of walk through it again, we just
did some simple math.
And once again, you remember I said, you could also just think of this as like two to the zero and
have K minus.
I set this equal to two to the zero.
And then came on to side could be set equal to zero.
Then you can end up with quite a side.
So the easiest way to do that as well.
And then this is just remembering these properties of the log and also the things that we said originally
in the base case.
So we basically got the I term simplified by trying to get IE equal to K get high in terms of K, that
helped us simplify the term.
And after that, we were able to use our knowledge of the base case and use our knowledge of logarithms
to get this back into terms of MN.
And then that led us to our time complexity after just looking for this term and getting rid of constants.
OK.
So after that recap, hopefully this multinational rule makes sense to you.
It's really just useful when you have a floor division in the recurrent recursion part of the recurrence
relation there.
So I wanted to point that out because I think it's an important, important rule.
And now that you've done this and that previous recurrence relation and kind of the basic recurrence
relations, you should now have a decent idea of how to go through these things.
All right.
So with that, I will see you in the next lecture.