day 3
Discuss here using the substitution method and may be after solving these three problems you will get an intuitive idea that how basically we can solve any recurrence relation using a substitution method.
OK, so let's get started with the today's session.
Here again we are having a recurrence relation which says that the value of T is something which is equals to one when the value of north is equals to one and.
The value of north is greater than one when the recurrence relation is T So this is a kind of a recurrence relation that we have.
Now again this recurrence relation we need to solve using a substitution method.
Now I am expecting everyone to please pause this video as of now, take this question and try to solve it on your own and.
Do let me know that what answer you are getting.
OK, with this I think now the approach, the way we used to solve any recurrence relation using a substitution method is already conveyed in the above 2 videos, right?
So the same method, same thing you need to do.
It's just that instead of substituting that N one or N 2, here we need to substitute the value of T So let's get started.
I hope that everyone already have tried it once.
So T is something which is equals to T plus the value of north.
Now what we can do is that we can try to solve the value for T It is something which is equals to T to the power 2 plus N 2.
What I am doing is that by seeing the above pattern I am just trying to what I can say substitute the value for T Now it means that what I am getting as.
T of north which is equals to T of north by two to the power 2 plus N by two plus the value of north.
That's what we are getting when we are trying to substitute here for the two times.
First time we are having this equation right?
This is for the first time.
Second time we are getting this kind of equation.
OK, this is for the second time.
Now for the third time what will happen is that we will be able to get.
Now we need to substitute this value T to the power two.
So here basically what will happen is that it's four, right?
Now we need to divide it again by two in order to do the substitution.
So it is nothing but is equals to T to the power three plus.
Something which we are getting as north by two to the power 2 plus N by two plus the value of north.
This is something which we are getting for the third time.
Now again the same question I can ask from you that how many times do we divide this value of two right again and again it means that.
At what point of time this N by two to the power K is equal to 1?
Because one is something which is the base case condition in our question.
This is something which is I can say base case condition, right?
If this is the base case condition, so this is what we can write here.
Now here if you will see N is something which is equal to 2 to the power K So the value of K is something which is equal to log of north base two.
This is something which we are getting.
OK, fine.
So here the value of T is something which is equals to.
It means that we need to repeat this same experiment log base two times.
Right?
So here T by seeing just the above pattern, I am getting a sense that it should be N by two to the power K -1 right?
Plus N by two to the power K -2.
Until so on and we are getting at a very end the result is north 2 N Here we can just try to replace this value of K with a value which is log of north base 2 which we have already evaluated.
So here the value of T is something which is equal to T of north by two to the power log of north base 2 + N by two to the power log of north base 2 -1 + N by.
Two to the power log of north base 2-2 until so on north by two N Now here if you will see what we can do is that we will be able to get the value as T Here what we can get is we can take the value of north as common and here again we are getting something called as one divided by again.
See why we are getting this one.
Let me try to.
First of all I think may be maximum students will not able to get an idea why how I am writing this.
So this north and two can be interchanged with each other.
So here what we will be able to get is north log of two base two and when the base and the coefficient that we have here is same the value will be equals to one.
That's why we are getting the value as north.
That's why we are getting the value as N here.
So north divided by north is something which is equals to 1 here.
Now what we can do is that we can write the same thing in this format 1 by 2 to the power 0 plus one by two to the power one until so on divided by one by two log of north base 21.
-1 How we are getting this?
What we have did here is that we have tried to just take the constants, focus on this part in the reverse order.
So what I did is that I tried to take the constant in the reverse order.
So it's north plus north by two plus north by you know two to the power two until so on.
Until N by two to the power log of N base to -1.
So what I did is that I just took the NS coefficient.
When we take the NS coefficient it will be 1 by two to the power 01 by two to the power one, one by two to the power two.
Until what value log of N base to -1?
Can I write like this?
I hope this is making sense right?
So basically this value will become T of one and this particular portion that I am.
Writing here we have written in the form of a reverse order.
We have written in the form of a reverse order so that I want to show you here something.
Here if you will observe this is something which we called as a GP series where the common ratio R value is 1/2.
How we can calculate the common ratio?
It is nothing but 1/2 to the power 1 / 1 to the power zero, right?
So here common ratio is.
1/2.
Now this is the sum of GP series where the value of R is less than one.
Now if you refer your you know I think 9th, 10th or 11th 12th classes here we have understood that the sum of GP series when the value of R is less than one is something which is equals to A into one minus R to the power N divided by 1 minus R This is the sum of a GP series that we have.
Now here if you will see what is the value of a.
A is something which is the first value which we have in our series which is nothing but one here because a is nothing but 1/2 to the power 0 which is something which is equals to 1 here.
Now what we can do is that T we already know is equals to one only.
It's a constant term.
So one plus what is the value of a?
It is one into 1/2.
to the power n.
Here if you will see what is the value of n that we have.
How many number of terms that we have?
Approximately equals to log of n base 2, can we write like this?
Log of n base 2 divided by 1 minus 1 by 2.
Here if you will try to solve this equation, this GP series equation, for sure if you will see here and obviously outside this there is aNorth term which is already in a in a multiplication term.
Now here if you will try to solve this particular series you will be getting a constant value.
So here what I am saying is that one any constant suppose which I am representing as one only into N is something where we need to take the higher factor in order to calculate the big O time complexity.
So this is something which we are getting as a big O of north.
So if you will try to see here, what we have did so far is that in any of the substitution method, whenever any problem is provided to you, the first step that that you have to do is that when just you have to look for a recursive term that what is the recursive term which is present inside my recurrence relation, right?
There is always some recursive term.
That's why there is a recurrence relation.
Now what you have to do is that you need to substitute that recursive term again and again.
But after.
Just you have to see the pattern here.
By seeing or looking into the pattern you will be able to get the substitution value.
But now you have the major objective here is to find out that what is the value of K.
This is very important to find out because until what point of time do I supposed to substitute in a substitution method.
This is what you will be able to get when you know the base case criteria or base case condition that what is the point where it is terminating.
What is the point where I should write this value as one?
Because I know when the value of north is 1, the value will be equals to 1 here.
So that's why we took like this as a base case condition.
Now with the help of these values you will be able to somehow get the value of K and until that point of time you need to write the values.
Now you always get somewhere or the other in a substitution method a series.
Which is a somewhere a mathematical series you will be able to get whether it is a AP series, GP series or any any logarithmic series or exponential series or may be sine Cos or may be sum of N natural numbers.
So these things you should know.
These are the very basic things.
So basic I am saying series you should be aware of.
Once you will get an idea about that, you will be always having that higher term.
You need to see the higher, higher I would say exponent term or higher term, higher degree, right?
So here you need to see that and whatever you are getting here will be your final time complexity that you will be able to get here, right?
That is the simple approach to solve any recurrence relation with the help of a substitution method and that is what I think I have conveyed with the past three videos which I have created here so that you will be able to get a clear cut idea that how basically the substitution method will work.
Now in the next upcoming video what I will talk about is that that how basically the recurrence relation can be solved using a recursive tree approach and when basically we should go for that particular method.
instead of going for a substitution method.
Ohh Till then, bye bye everyone, stay tuned and
Comments
Post a Comment