OK, so now that we have gone over how to solve for the time complexity of iterative algorithms, it
is time for us to look at how to do the same for recursive algorithms.
So I know we didn't go super deep on the iterative algorithms, and I'm not going to go super deep on
the recursive version today, but I will be including more examples after this.
The last lecture and this lecture and kind of just meant to introduce you to the tools that we use to
do these more formal analysis of algorithms.
So we'll I'll give some examples of some more difficult summations and things and some more difficult
recursion things.
We're going to talk about today after these two lectures, so you will have a chance to practice similar.
So with that, let's get into how to solve for recursive algorithms.
So how do we analyze recursive algorithms?
Well, rather than just using the summations that we used before, we can use something that better
models the recursive pattern to solve for the time complexity.
And so a useful method for this is to use something called a recurrence relation.
And an example of recurring insulation.
Is this right here?
So this might look a little scary if you don't like math stuff.
But don't worry, we're going to go over this example, the rest of the slide show.
And so we will look at it in quite a bit of detail, which will help you understand.
So let's dissect that example.
I'm using some color coded pieces of the formula and relating it to the explanation just so we can understand
the connection between the two.
So here we're asking how much time is taken to solve a problem of size and that's represented with the
yellow T event.
So the T is for the time taken.
And in the parentheses for a problem the size of an.
And that is when the problem has a recursive call that reduces the size of the input by one.
So that would be this green thing right here, that's the recursive call, reducing the size of the
input by one.
And there's a single instance of our chosen basic operation, which is plus one that happens each time
the function is called.
So this is our basic operation.
As you'll see in the next slide, I came up with the code that goes with this recurrence relation.
There could be multiple functions and multiple pieces of code that might relate to this recurrence relation,
but I have an example in the next slide and that I've chosen multiplication.
So we're just choosing a basic operation.
And this red thing is representing the basic operations, the number of basic operations that we're
adding per call of the function.
We also note that the time taken to solve a problem of size zero is zero.
So that is our base case right here.
So T for time taken to solve the problem of size zero here in the parentheses is equal to zero basic
operations.
And so let's see why that is.
In the next slide.
So here I have a function called Ecsponent, and all it really does is take a number and raise it to
the in power, which is also passed as an argument, and it does that by recursively calling the function
and multiplying acts with itself, basically and then as a base case, if any, zero return one.
So look back at our recurring situation here.
We live in minus one in the green.
Right here is our recursive call we were talking about.
The plus one is for this basic operation, which is multiplication.
That is just what I chose for this.
I chose to solve for the number of multiplications in this algorithm.
And so that is what I'm considering for the time complexity I have chosen the basic operation, its
multiplication.
And so that's why there's this plus one right there because we have one multiplication.
And the base case of zero is right here, so if an equal zero, if the input size of the size of the
problem is zero, then there will be zero multiplications.
Right.
Because we chose the multiplication operation and there's no modifications here.
So I'm putting zero.
You might be thinking, OK, well, this is a constant operation, so we could be adding this and you
could.
But like I said, I chose modification.
So I'm counting the counting, the number of multiplications.
And even if you did have you know this to be one, you would still end up with a similar time complexity
and we could maybe look at that at the end of the lecture.
But for this problem, at least you would turn out at the same time complexity.
So.
But we're just looking at T zero zero because we care about loan applications right now, so to solve
this recurrent solution, we're going to use some simple repetition and substitution until we can find
a pattern.
Then we'll use that pattern to come up with a better formula to solve for the time complexity of the
algorithm.
So if we take a look back at recursion, basically what we were doing in recursion and needing to keep
breaking the problem into smaller and smaller problem until we reach our base case, and then that means
that we need to.
We then have the means to go back and solve our original problem once we know the base case.
So an example of what I mean by this in relation to our recurrent formula here is I'm looking at T of
N right now.
T event equals this, but it would be like asking the question, well, what is T of N minus one?
Instead of to give in and that that's what we're going to do, we're going to kind of keep repeatedly
asking this question as we.
Ripley, substitute things into this formula, we keep asking what is TV minus one, what is tier one
less than that, you know?
And so let's go ahead and start out.
So we're going to substitute minus one for in in this so we can ask ourselves what is T minus two minus
one?
So I have put the original formula up here and read just to have it as reference.
And I'll be doing that in the next few slides as well, so we'll be able to refer back to that.
So here we are, substituting and minus one into our original formula, so we have T minus one instead
of in and we've substituted here in green.
You can see and that ended up giving us a result of of a minus one is equal to T of minus two plus one
because we have these two minus ones there.
So we want to know what you mean.
Minus one was then we substituted for in and we ended up with these two right here.
So great that we got that.
What do we do now?
Well, we now know what you mean.
Minus one is so what we can do is substituted back into the Formula T of in where we left off and simplify.
So since we owe to you and minus one is this we can replace DeHaven minus one or we left off with this
light blue right here because that's what we figured out in the previous slide.
And if we simplify that, it gives us T minus two plus two.
So what do we do now?
Well, we just continue this process, actually.
We're going to keep asking, well, what is one less again?
So we said T minus one.
We wanted to know that now we're at T-minus two.
So let's ask the question, well, what is T then minus two?
And then we're going to try and solve for that.
So let's try and solve for T of and minus two.
So here's our original formula.
This is where we left off, we said TV Nichols TV minus two plus two.
So what we're going to do is substitute in minus two in our original formula now.
So putting in minus two instead of in.
And that gives us T minus three plus one.
And then just like before, we're going to take that answer and we're going to substitute where we left
off.
So we're at this point right here.
So now we we know what T of in minus two is.
You can imagine that's right here, too.
I just put this equals sign saying no to unless two equals this and then we simplify it.
And so it was this.
So this is T even minus two.
And now that we have that, we're able to substitute it.
We don't need this to even minus two more, we because we have this now so we can continue on.
So I'm replacing.
TV minus two with this blu ray here, which is this.
And that's what you see right here.
And then we simplify that, and it simplifies to TV minus three plus three.
So let's continue on the time.
So original formula up here, this is where we left off right now, we're going to say, Hey, what
is TV minus three?
Let's figure that out.
So TV minus three.
It's basically here we're doing it in our original formula.
So we're seeing in minus three instead of in.
So T of minus three, minus one.
That's going to be a minus four.
And then we have the plus one.
So we're substituting minus three.
We end up with this.
And then that next type of substitution where we use this blue.
We're basically going to go where we left off in the formula for Kevin, which is right here.
And we are going to substitute this answer we got right here, so TVN minus four plus one in the formula
where we left off.
That gives us.
We have this one in the story here.
TVN minus four plus four.
And so maybe you don't see a pattern.
Maybe you do already see a pattern, but that's what we're going to look into now.
So what we're interested in is finding a pattern for something we call the eighth term.
And what that is is basically just taking a look at all of the results of the blue substitutions we
were doing.
So those again, the results were yellow.
So I'm going back one slide.
I'm talking about this substitution when we substituted these blue things in the formula here where
we sold for it and it gave us these results.
This is kind of where we keep saying, Oh, where we left off, where we left off.
Now we're at this point, this is where we left off last.
So we look at all those yellow guys there.
We're basically trying to look through all of those, so we start at the beginning, this is our original
formula.
Then we had and minus two plus two and minus three plus three and four plus two.
We want to find a generalization of the pattern and put it in terms of AI so that you might be able
to see a pattern here.
And I definitely do.
And on the next slide, I'm going to show you what that is either.
So instead of just two and two and three and three and three and four four, I notice these are the
same numbers.
So what I'm going to do is actually just say teven minus AI plus I.
So you can imagine that, like if we're on this ice iteration of us doing the recursive process, you
know, we had one and then we had to.
So our I was two and I was three and I was four.
Basically, I can say, you know, when I was two, when we were on our second.
Kind of repetition of this whole process of substitution.
And I was to say a second repetition of this whole process.
Then it was also a two right here and a two right here.
So I'm going to say when we're on the eighth repetition of this process, I can basically say that there's
going to be an eye here and here, and I make this generalized formula.
And so great now we have this generalized formula, so what's the really the point?
How does that help us?
Well, what we're going to do now is actually get back to our base case.
So let's think about our base case.
So I've kind of been putting that off sometime.
You noticed it was right here.
But we've kind of just been solving and messing with this stuff right here.
Now we're going to look at this T of zero equals zero.
So what I want to do is use this base case in conjunction with our new iith term to see if I can get
the IV term back in terms of in because we really want to solve for N in the end, because we were interested
in the time taken to solve the problem with an input end.
Remember, that's what we originally asked.
So now what we're going to do is use this base case to help us get this right here back into terms of
n so we can finally solve for our overall time complexity.
And so what I'm going to do is I may say, OK, well, this is T of zero when the problem size is zero
and I'm just going to I know that what's in the parentheses here can be considered when the problem
size is, you know, the eighth term.
And so what I can actually do is, I can say in minus II is equal to zero.
I can assume we're at the base case.
Right, so I can assume, OK, I'm going to go ahead and say that we are at a point in time when the
problem size is zero because we know what that is.
And so I'm going to say, all right, well, then n minus II equals zero.
So what I can do then to get it in terms of in.
Is I can simplify this by not really simple, I would rearrange it, I can add I on this side and I
on this side too.
And then we get something in equals.
I know now we basically can put it in terms of in right because we found out that I not only is an equal
to I, but it goes this way too, of course.
So I equals in.
I can replace these ideas within.
So let's go ahead and do that now.
We substitute in for AI and our generalized AI term formula.
So T event equals T of N minus N instead of AI plus N instead of AI.
And you might see this right here.
And minus in something minus itself is zero.
That's pretty interesting because we know this right here.
So if we have that, this is kind of just a little recap right here.
But if we know that, then we can say, OK, well, that's T of zero right says to zero plus in, oh,
well, remember, let's jump back here.
Our base case T of zero, we know what that is.
It's zero.
So instead of putting T of zero here, we can just substitute two zero four two zero because that's
what it is.
We we we know that that's our base case two zero zero zero.
When we do that, we're left with just here then equals in.
And at this point since we just have to then equals.
And that was what we were asking in the beginning, right?
How much time did it take to?
How much time does it take when the input is in?
You know, the problem size is in.
And right here T of any equals in, that's a solid answer.
Now we can actually say that we have an exact bound on this area and we can say that the time taken
is theta.
And so we have a tight bound.
And so, you know that if we have a tape bound on this, then we also could potentially say big, oh,
you know, we kind of.
You know, state is a little better because it's a more exact bound.
But if we wanted to, we could also say Big O event, right?
Because if you think back to how we were bounding the functions and that lecture, we said that the
Big O was an upper bound and so it was greater than or equal to the function and consideration.
And the key is equal to, you know, greater than or equal to.
And so since this is a time bound, you know, we could also say that it's big of an because the tie
bound is something equal.
You know, it's it's a it's a tie bound is bounded upper and lower.
So we could also see a big event.
But this is kind of nicer to have Theta.
And so hopefully that helps connect our bound to that a little bit.
And hopefully this was enough to explained the general way of solving these recurrent relations.
And like I said, we will do some more examples.
I'm going to go ahead and write some up so you can look over those and I'll have some notes that way.
You can see some other solutions for some slightly more difficult ones.
This was a pretty basic one right here, and I'll try and do some for some patients, too.
But with that, I will see you in the next lecture.