Hello all and welcome back.
So in this video now let us continue our discussion and found the space complexity of Fibonacci number.
Right.
So again this is some algorithm which we have done a lot in deep.
We have drawn its recursion tree.
We have found the time complexity.
Now let us talk about the space complexity of this particular algorithm.
Right.
So let me first write down the code Fibonacci series.
We used to write the code something like this.
So def fib let us say nth number if.
It is less than or equal to one.
We used to return one else.
FIB of n minus one plus fib of n minus two.
Now here again everyone.
If you will see we are not creating any variable as such.
Like not a single variable at all.
And no particular.
I would say this thing, uh, any array or any list.
We are not getting anything, we are just making the function calls.
And if the base case is there, then we are just returning.
Right.
So now how will you are going to calculate this.
So let us employ one thing again.
So if you will see this is the major thing right.
Which is kind of a case which is going to get called to understand how we are going to find.
Let us make the recursion tree again.
We will be getting our n here okay.
Now one thing to understand here, if we understand the whole recursive relation, the one which you
have written first, the whole n minus one three is going to get called, right.
So first this particular tree is going to get executed.
Basically this particular half of tree this one.
Once we complete this tree then is when we are going to move to the n -2 or 3.
Right.
So we are not going to make them altogether know.
First, we know that this whole part of my tree is going to give me the answer, and then I am going
to make the call here.
Right.
This is something which we have seen in recursion very closely, that first where you are making the
call based on your recursive relation, the number of the function call sequence.
Right.
I showed you how this is going to be the first call.
This is going to be the first.
Then this is going to be the second, then third, then this will come back.
So something like this used to happen right in a very similar manner.
We are just going to make these calls.
And when this left sub tree gets the answer then we are going to move to the next part right.
Now one thing to always remember we are not going to make the calls simultaneously or n minus one and
n minus two.
Let us see the example for this.
Let us say maybe with the four.
So for four now it is going to make the call to three, then two, then one.
Right now if you remember, if you understand and see one thing, this is the maximum number of functions
call which are there in my memory at a point, right.
Once this gets done, I am going to make two zero.
Okay.
So there are also there are four calls.
Now when this returns I am going to make this call.
And here you will see just three calls are there in my particular function in a particular time.
Right.
So on that note, this is going to return.
And finally I'm going to make the call to two.
And this two is going to make the call to one.
Right.
This is also three calls at a time.
Then it's going to make the call to zero.
This is going to return again here also we have the three calls at a space.
And then this is going to return going to return.
And finally we will return an answer.
So the point which I want to actually show you is that at a in this tree at a point the maximum calls
are this green one right.
Maximum number of calls in memory.
So it is this green one.
If now I say that okay each function is taking some k space, then I can very comfortably say because
these are n calls you will see that okay it is going to n the space complexity is going to be n k okay.
So that's how we calculate it.
Now let me show you this again using Python tutor so that you are able to understand, let's say now
fib.
Let's say fib n plus one.
Sorry n minus one plus fib of n minus two.
So here again what I want to focus.
What I want you all to focus on is that how many calls are in the memory.
The maximum functions are in the memory right.
But this has not changed to Fibonacci.
Right.
So pay attention everyone.
Now I make this and make the call Fibonacci of four.
Then I'm going to make the call to this left.
Right.
Just first I'm going to make this call.
I'm not going to make the call to two.
I'm going to make the call to three.
Now this three is going to make the call to two.
And now it's going to make the call to one.
At this particular point I have four functions in the memory.
And if each is taking let's say k space then I can very surely say that okay, my space would have increased
something like this one function two.
Function three.
Function.
And finally four functions.
Right.
So this is something which is the maximum as of now.
Let us see what else is going to happen.
Then I move forward I get the answer.
So this is actually out okay.
So when I repeat this I return this.
The second Fibonacci call gets the answer of this particular call.
And it is now going to make the call to zero when we make the call to zero.
Again there are four functions in the memory right.
So this is kind of pain.
But now you will see that calls are going to get reduced.
So once it returns zero okay.
Now I have three functions with three functions.
This is going to reduce.
This whole thing is going to reduce okay.
Then again I have three functions.
So it is going to be the same only once it returns I have two functions now.
So I think you can imagine.
All right.
So it's going to be the same then.
It's going to be for two.
Then two will only be there then return.
So something like this is going to happen.
But the point which I want to make is that at one single point, at one single point, now you see that
there are three functions.
So maybe this will jump.
But the overall idea is that never will I will.
I go above four functions at a single time.
So this is what I was saying, that we have to always see the peak memory.
Because yes, you might be making somewhere around two to the power N calls, but that doesn't mean
that all of them are taking your space all at once.
No one function gets created and then gets destroyed, so the space is freed up.
Okay, so again, that is very important to understand.
I will repeat what I just said.
When a function is created and destroyed, the space space overall is freed up.
It's the same as let's say in your pendrive.
You copied something and then you just deleted it so the space is freed up.
You cannot say that.
Okay, this is still taking up the memory.
Okay?
You will be actually considering the memory when everything is there.
What is the maximum memory which reached right?
That is the overall space complexity of the any anything which you are doing.
Okay.
So because each and every of these functions, when they get deleted from the scope, the space is freedom.
I will just be seeing the peak memory which is used.
Okay.
And this thing is very, very important to understand everyone as well as to explain something which
not all students are aware of.
Okay.
So please make sure that you are able to understand this.
And once I actually now continue my whole work, never will.
You have four functions.
Now that is the whole understanding.
See three are there again.
Three are there, then two are there.
And finally I get my answer.
So this is the point which I want to explain you with respect to this recursive relation and call.
Now again, the understanding here is that you should be very much comfortable in recursive making the
recursion call as well as one second.
Okay.
I think I called it.
Yeah.
Cool.
So I will draw the memory here as well.
So you should be very much comfortable.
And that's the reason I was always pushing you to write the recurrence relation.
Right.
Always I was pushing you to write the recurrence relation because we are going to get graph something
like this.
Then it is going to increase then going to increase, going to stay the same, then three, then maybe
two, then again three, something like that.
Of course you can make it should be fine.
Okay.
Again I'm not drawing it perfectly, but I hope I get the idea across and I am majorly interested in
this memory.
Okay, So yeah, that's the overall way we find out.
So let me write down the answer.
Finally, space complexity
is big O of N because it will be n k n k.
I can always write less than k plus one n.
And now you know the voltage.
This is going to be my g of n.
If this is my g of n, then I know my space complexity is O of g of n.
So everything, if you will see, is getting connected to the introduction which I gave.
Right.
So that's the reason if you understand with this flow right, your understanding is going to be actually
unmatched.
Cool.
I hope this was clear.
Everyone.
Again this is a little tricky.
We request you to see this once again.
If it is not clear it should be.
I have shown you using the visualization as well, so please make sure that you actually understand
this and employ this when you are finding the complexity for recursive calls for rotation.
Again, this should be easy.
Okay, so yeah, let's meet in the next video and we will see what else we can understand about space
complexity.
Thank you.