Hello all and welcome back.
So in this video let's continue our discussion and now find space complexity for some algorithm which
we have studied.
So let's get started.
Now when we have to find the space complexity we have already discussed on the basics like what exactly
do we consider in space complexity and majorly what all we can control and what we cannot.
For example, input space.
The input which you are getting is something which we do not have any control over, but auxiliary space
is something which we can actually control as well as, uh, I would say optimize on.
Right, as well as if, let's say some algorithm is there where we are, let's say creating lots of
those arrays.
Okay.
Now if you will remember, when we were doing recursion, right, there was a reason, when I was saying
that, let us use the indexes like I and J start and these pointers instead of slicing our list.
Right.
The reason for that was actually that when you slice your list, it creates a copy.
So in a way some space is getting used for that particular copy in your algorithm.
Okay.
So we're going to use going to look at that in recursive part.
But for the time being, let us now focus and first see for the insertion sort we already discussed
on the bubble sort in the last video.
So let us see the code for insertion sort as well everyone.
So this is the code of insertion sort which is front of us.
Now here if I say if I see then we have just created some key, some J, then I am letting running some
loop and doing some operations.
Again.
J is created here, but that will be that is basically updated from this scope.
Right?
And finally I am just updating.
Okay.
So I don't see I have created any new memory here apart from these small small variables key and J.
I do not think any major memory we have created, which is dependent on the length of my array, right?
So does not matter if I give it a three element array or 3 billion element array, it is just going
to create these elements and going to work on that, right?
On that note, I believe that it should have a constant space.
So o n of zero it is not dependent on n which is equal to o one.
Right.
On the same understanding, if, let us say now I have some loop.
Okay.
Let us say I am given some array only array and I need to find the maximum and I need to find some,
find the maximum of this array.
So I am going to do something like this for I in array.
If my array of I is greater than answer, then I can just say answer is equals to array of I right?
Again, if it is in a function, we can return, else we can print.
So that should not be a problem.
If you will see here.
Again, we are not creating any new memory which is dependent on the size of my array.
Right?
I am just actually creating an answer variable which is very small, which is constant as well.
So here as well here is when we will be creating Only O of N zero space, right?
I hope that is pretty easy to understand, right?
Like, we are not creating any extra memory and I have already told you these small variables, they
don't have a part to play as such, right?
So the understanding is that all these algorithms, they are constant space algorithms, your bubble
sort, insertion sort, selection sort, all these are your constant space algorithm for algorithms
where we have written code iteratively.
It is pretty easy to find.
Just see that if you are actually creating copies or creating something based on your input which you
are getting, if you are creating some extra space, not these small small variables.
If you are creating some extra space, then that is where actually you should say that yeah, you are
using some memory.
It is not constant.
Okay, cool.
So if that is clear, let us actually move to the major part, which is space complexity.
Of our recursive algorithm.
Now coming to recursive algorithm.
Let us write the code for, let us say factorial of a number.
Write some some algorithm which we have studied.
So coming to space complexity of recursive algorithm.
For factorial let us say for finding out factorial of n, I am just going to write the code something
like this.
Right?
So def factorial of n.
If my n is less than equals to one, then I can just return one.
Else I just return.
Factorial of n minus one.
Right.
So something like this.
Actually I intend to do.
Now here if you will see, we have not even created a single variable, let alone any array or list
which is created on the basis of my factorial.
So should the complexity here be o of one?
Well, if you are thinking like that, then again we have to revisit the way we did our time complexity
analysis of recursive algorithm.
In recursion, we have to make sure that we can also count exactly what is happening when we go inside
this when this call is made.
Yes, we are not creating any particular variable, any particular array in the working.
But this return factorial, right.
This actually will be invoking another function call.
And this function call will be waiting in the memory till then.
If you remember, if you remember then I showed you and I'm again going to show you this in Python tutor
as well, so that you are able to actually visualize pretty nicely that these functions, they remain
in the memory and they are dependent on your end.
So for example, if let's say I am calling for factorial of ten, then I will have some function which
are going to wait and that will be dependent on n right.
So if n will be ten then I will have ten functions waiting.
Right.
As compared to, let us say some, if the function call were some constant, then I would have said
that okay, it is anyway zero and zero.
But here let us see how we are going to find the same.
Okay, so exactly what I am saying.
Let me show you that as well.
We are going to make a function call for uh n right.
And this function, let us say takes up some k space right now because this function is calling another
function beneath it which is going to be n minus one.
Then let us say n minus 2... all the way till one where it is going to return.
I think spaces from this should be considered, and let me show and help you visualize this as well.
So let us go to python tutor def factorial n.
If n is less than or equal to one, then we can just return one, and else we can return n into factorial
of n minus one.
Right?
I think I didn't write uh, this here.
So one second.
So we are not creating any new variable as such.
We are just using what we are given.
And let me just use factorial of five maybe.
Yeah.
And I can just print.
So we see the answer.
What should be fine.
Cool.
So let us now try to execute it.
We have seen this many times.
Like we will have all these methods right?
Which will be waiting.
So let me just zoom it a little bit.
Yeah.
Great.
So first this factorial is created in global frame.
Next if we move forward factorial with n is equal to five is created.
Moving forward again factorial with four is created.
But one thing which you will actually notice here is that this five is still in the memory.
It is taking up some space, right.
And your function, these number of function that is dependent on n that is not some constant.
Okay.
So let us move forward three two and finally one.
Okay.
So at this particular point at this particular point I have five functions.
If n would have been ten, then I would surely have ten functions waiting in my memory.
So the point which I want to explain to you is that the number of functions waiting in your memory,
it is not some constant, it is dependent on your input n.
It is very, very well dependent on your input n.
Okay, so for example this n if it is 100 then I will at some point have 100 functions waiting.
If it is 1000, then 1000 functions waiting.
It is changing with respect to my n and thus let's say if I am saying that hey, each function takes
up some k memory, then I can say very comfortably that k n is going to be my space complexity.
The reason is that I have n functions waiting to get my answer, and you will see that once this s function
like let's say these are the n functions, that would be the maximum in the memory.
Okay, so one thing more which we have studied.
If I see what the graph it's going to be something like this.
It's going to increase increase increase going to reach out to the maximum Okay when your n is equal
to one and then decrease.
So I have already told you that how we take the peak memory.
Now I am not going to add all these memories, okay.
They are intermediate memories.
So at a peak level we will have n functions waiting when n is equal to one.
And thus I can say very comfortably that n into k is going to be my space complexity.
So let us write the same down in our notes as well.
Okay, I hope this is clear.
By seeing this visually again, everything is going to get written and I am going to get my answer.
Okay, great.
So what I am saying is what I want to actually say is that recursion.
Let me write it in some box.
Yeah.
One second.
Yeah.
Recursion is not free.
And this is the reason why I was teaching you recursion.
I told you about the recursion limit, about the stack memory, all these things.
Right.
So we have this limit so that the overall stack memory that doesn't get, uh, over, uh, stack overflow.
Right.
That's where Stack Overflow comes into picture as well, the popular website.
So yeah.
So recursion is never free okay.
The functions.
Waiting for answers.
Takes up some space.
And because the number of function calls is not is dependent on my n, it is not constant.
Hence, I will always say that I'm going to take that much space.
So this is going to be my time complexity, right?
So let me just draw this as well everyone, so that you remember please make sure that you download
this notes.
These will be provided to you and will be very helpful in remembering or revising when you want to give
any interview or anything, right?
That's why I'm making sure that I'm writing each and every thing.
So at peak we will have n is equals to one and n functions.
Waiting.
Right.
So we will have n functions waiting here.
And n is going to be one.
So again recursion is not free.
Some extra space is required.
Now we have already seen for iterative based algorithm which you should be very very easy to calculate.
Let me show you one more algorithm.
In this video only.
So that is going to be binary search.
Okay.
The way we do binary search by recursion.
Binary search by recursion.
Now here again we have done this analysis a lot of time.
We will be given an array okay.
At each point I am going to divide my problem.
Second.
I am going to divide my problem into half.
N n by two.
Let me make it half one second.
In by four.
Something like this.
Right.
So again the understanding is the same.
If each of these functions let's say they are taking up k space in my memory.
K k k.
Then if I am able to count the function calls okay.
And again one thing more.
Remember like I have to tell, I have to count the total function call which will be maximum at a point
right the peak.
So if I can count all these things okay, then I can say my answer is going to be something like this
k into number of functions.
If that is the case then we have done this a lot of time that how much are these functions going to
be?
If you have not seen the previous video, please go and see that.
Uh, we have done this calculation.
A lot of times it's going to be n into sorry.
My bad.
K into log two to the power n again.
The basic understanding is same, only we are calculating it for the worst case, right?
If you find it in the very first place, then again these function calls are not going to get made right.
So always remember we are calculating the O big O which is the worst case, something which you have
studied.
So the same feature, the same overall concept get extended to the space complexity as well.
And in worst case and in worst case we will have.
Log n functions waiting.
Right.
Now, many of you might be thinking that recursively binary search will have some complexity.
Yes, absolutely.
The same is not true if you do it iteratively.
And this is the reason many times in very, very optimized environment.
Right.
Let us say if you give some OS or do some questions on let's say LeetCode or some other website.
Many times it can happen that your recursive solution might not get accepted because let's say the input
is very large, right?
But your overall solution for this iterative will not get accepted.
Okay.
And that's the reason for that particular thing.
That space is also considered right.
So it is not that recursion is free.
So many times you will see that you will get some error if you try to just submit the recursive solution.
But on iteration the same solution is going to get accepted.
The reason is they are going to be space complexity, not the time complexity.
Okay.
Because time complexity for both of them are same.
Now it is the space complexity which is giving you the problem.
Okay, so I hope that is clear.
Everyone.
We are going to see that at a lot of places.
And that will actually one of the reason we study about deep as well.
Right.
So I'm going to when I'm going to teach you deep in the module, then you will also understand why deep
is required and how it is helpful in space and time complexity.
Both.
Okay.
But yes, don't feel like if your solution is not getting accepted for recursion.
So recursion is not useful?
No.
I think till now we have seen that how recursion help us to even think the thought process overall,
right?
How to write easily the code.
And then we can of course easily even transform the same into iterative solution or something.
Right.
So it's not that recursion is bad, it's just that it has some space complexity caveat behind it because
functions are waiting in the memory, right?
Cool everyone.
So I hope this is also clear.
The overall understanding and again, not just giving you it directly, making sure that you understand
the whole process.
That is something which I want all of you to pay.
Focus on process is the most important thing because if you understand the process, it's going to stay
with you and you can find every answer for even some algorithm which you have never written or let's
say, which you are trying to write.
So remembering will not help you to understand these things.
Understanding the process will, and that is something which you can even use to explain your interviewer
tomorrow.
So please make sure that you always and always focus on the process the way I am teaching, and you
will be able to crack any of your product based companies or any company interview for that matter.
Okay, cool then everyone, thanks a lot.
So let's meet in the next video.
Thank you.