Hello all and welcome back.
So in this video let's do one more question on space complexity so that your understanding is actually
unparalleled.
And you will feel a lot more comfortable when finding out space complexity of any algorithm going forward.
Right.
So the algorithm is again, something which we have done very much in depth merge sort.
Okay.
There's a small caveat here as well which I want to explain.
So please make sure that you understand this properly.
Now in merge what we have done in multiple times, we are again given a list okay.
We divide and make the calls on n by two, n by two okay.
But again the understanding here is that I am not going to make this call simultaneously.
I'm going to make the call first on the left half.
This is going to make the call on n by four.
Right.
So let me write this n n by two n by four.
And one second.
N by eight.
And like this okay.
Once this left subtree actually completes its whole working.
So first left subtree.
Is going to run.
And now we have seen this a number of time that how many of these functions right.
Function calls are going to be in the memory at a time.
So in the case when I am dividing it by n n by two, n by four, n by eight, at a maximum point I will
have log two of n functions.
Call waiting right.
Again, this we have seen at a lot of time.
Binary search merge sort time complexity.
Everything functions at max.
Waiting in the memory.
So for the recursive call for the recursive call, this is actually something which we know that at
least the space complexity is going to be log two of n okay, because we know that these many function
calls are waiting in the memory, right?
But if I just quickly write the overall code for your binary search, if I quickly write def, let's
say sorry a merge sort my bad non binary search merge sort.
So we are let's say getting an array which is writing the pseudo code.
So we used to actually call on call merge sort.
On left part.
Like of course we can make this left and right.
That should not be a problem.
Merge sort on right part.
Okay, now I have actually found out my space complexity for this particular operation.
The recursive calls, right?
So I know that from recursive call.
From recursive call, my space complexity is going to be log two of n that I have actually established,
because these many functions are going to wait.
In the worst case scenario, these many functions are going to wait.
And again in merge sort anyway.
We do not have any best case scenario as such, right?
All always the whole process gets worked on.
Even if you give it a sorted array.
But is there anything else which can cause a bottleneck or which is more memory intensive than this?
Well, let us see the same thing once.
Then we also do the merge function, right?
Then we do the merge function where we merge these two sorted halves.
Now if I talk about this merge function in particular, what it does is you have this n size array right.
You send it to n by two n by two size array n by two, n by two.
It now creates one extra array which is normally n in size, normally not like.
Of course it is n in size, not normally.
And then you just copy everything from this right.
So this is how the merge sort actually used to happen.
We have again discussed and coded a lot of time as well.
This is your auxiliary space.
Auxiliary space right.
This you are creating to solve your question.
This is not just your input part okay.
This is not just your input part here again.
What you're going to do, what exactly are you going to do is in this merge function you are creating
the.
So how I can write it is that this is using your log two n and this is using your n.
So if I actually now try to add up the space complexity, I can say that hey, my space complexity seems
to be something like this n plus log two n.
Again, you can add k in front of them that doesn't have.
That is not a problem.
Your you will be doing some using some memory in merge recursive call some memory in the merge function.
That is fine, but again the understanding is that if I compare for a very big n for.
Let me write this in white.
Actually, that is clear one second space complexity.
Okay, it is going to be o of.
Again, you do not have to multiply them.
Please remember and understand this thing.
They are happening in parallel inside.
It is not happening.
And one more thing you have to understand.
Let me explain you that as well.
So when it gets cold, right when it gets called for, let's say n by two, when it gets called for
n by two.
Here also we will be creating this subarray here also, we will be creating this auxiliary array of
size n by two.
But this is going to get destroyed right.
This is going to get created and going to get destroyed.
So yes we are going to create multiple of these subarrays.
But at a single point in memory, at a single point in memory, when I will just come out of all the
recursive calls, this will be the largest, sub, largest auxiliary space or auxiliary array which
I am going to use.
So it's not that they are going to wait in the memory.
These n by two, it's going to get created.
Yes, but it's going to get destroyed as well.
So it's going to free up space.
Okay.
And at a single point you will just have n by two, then n by four, then n by eight like this auxiliary
space.
But they are going to get destroyed.
So if the space is going to get freed up okay.
So on that note, you have to see the maximum space at a single point, at a maximum space at a single
point.
The peak.
And due to that particular reason, this is where the peak will occur when the merge sort we are calling
on the main array where n size of the space will be created.
The n by two n by four auxiliary space.
Yes, that will be created, but that will be freed up as well.
So I'm not going to consider that at a single point.
The peak space is going to be for the auxiliary space of array of size n, right.
I hope this is clear as well.
Everyone.
It's the same as let's say you are adding small small files but maximum files which you are adding,
right?
You are adding, let's say a file of one GB deleting it, two GB deleting it, three GB deleting it.
But when you add the file of seven GB in your eight GB pendrive, that seven GB is the peak.
That is what your overall space you want free.
If you want to just redo all your operations right.
If you want to add and delete all these things again, that is what your space complexity is.
In a very similar understanding, in a very similar understanding, you will be adding them because
they are parallel.
They are happening one after the other.
another.
Okay, they are not happening altogether with each one of them.
Okay.
So in that manner, in that manner, all these n by two or n by four, one space is going to get destroyed.
At the end of the day, I will just have my space complexity like this.
If this is my space complexity, then what I can do is for a very large n.
N is going to be a lot large for log two n.
We have already seen this.
For n is equal to 1 million.
N is going to be 1 million.
1 million only.
But log n is going to be somewhere around 20 right.
If I remember right that was what we calculated.
So ten to the power six something like that.
Yeah.
Something 20 like log two.
I hope it is taking log two only.
Yeah.
Log two okay.
So if that's the case then again I can just ignore the least dominant term.
I can just ignore the least dominant term.
And I think I can very comfortably say I can very comfortably say that.
Hey, this is going to be my major term.
This is going to be a major term.
And thus I can write.
My major term.
Is n.
So let's say now some k space is taken in your merge function.
Then you can write it k n okay.
Is your space complexity okay.
Because that is going to be the maximum k n.
And now you can very well say that o of n is the space complexity.
Of merge sort.
Right everyone.
So again understand this very very nicely that this log to n this is in parallel to that.
Like first this get used up and then this get used up okay.
It's the same as this is going to get used up and this is going to get free.
So my graph is something going to be something like this.
again.
I'm just going to draw it so that you understand this thing.
Okay.
I'm going to have some memory going to get used.
Okay.
First recursion is going to get using the some memory.
Okay.
But this is anyway going to be a lot less as compared to let's say when n by four gets n by four auxiliary
gets created.
Okay.
So this is going to take a peek.
Okay.
Then again the recursion memory is going to be a lot lower.
You can understand that n by two at any point of time for high values is going to be lot greater than
log2 n right.
So log2 n the recursion space is going to be very less.
And finally I'm going to actually create an array of o n space.
This is going to be my peak n a of o n sorry a of n space.
And because I am just worried about the peak, that is something which I'm going to take.
And actually the peak is going to come towards the end, like it's not going to be like this.
The reason for that is once you make all the calls, that is when you are going to work on your merge
function, right?
So your peak is going to be in the end here.
So what I mean by that is if you see the code again, once all of them keep completing their work,
right.
So inside of these functions first you are going to make the calls.
Then it's going to make a merge function call inside them as well.
In the end when everything is being completed, that is when I'm going to use my n and create an n space
auxiliary array.
And that is going to be the maximum one here.
Maybe n by two is created here, n by four is created.
Something like this will be happening.
But in the end, once I've gotten all my answers, that is where I will be using this particular thing.
Okay, so yeah, I hope that was clear a lot.
Everyone, please make sure that you see this again.
Let me show you this website.
Yeah.
So now I think, uh, these will also make a lot of sense to you, the space complexity.
Right.
If you will see for me it is o of n only.
And I hope now you are able to understand why it is O of n and why all these complexities are n log
n.
Right.
So now you will be able to make sense of a lot of these algorithms.
See bubble sort, insertion sort.
Selection sort o of one.
I will ask you to just do for quicksort some algorithm which we have studied.
It's going to be a lot easier as well for quicksort.
Okay.
The space complexity and the overall time time complexity is also you can find for some of the data
structures which we are going to study going forward.
All this will also then make a lot of sense.
So you do not have to worry on that anyway.
Okay.
So yeah, I hope now this sheet will be around 4,050% clear to you.
Towards the end of this, you will be able to understand 80% of the sheet very easily.
Okay.
Again, your aim should be to understand the basic principles, not to understand 100%, because that
is not what will get you interview.
Get your interviews clear, right?
So cool then everyone, I hope this was helpful.
You are able to actually understand the space complexity.
Different ways to find out that a lot nicely.
Again, please make sure that you revise them okay?
Space complexity is also asked and many times again you have to understand if space complexity is the
reason behind your code failing okay.
So yeah, let's meet in the next video.
Everyone thank you.