Hello all and welcome back.
So in this video let's continue our discussion and now understand with space complexity.
So till now we have understood about time complexity a lot.
Well.
And in deep we have actually find out the time complexity of many algorithm which we have studied.
The worst case.
The best case.
I have given you an assignment as well in which common codes which you write, you will be finding the
accuracy or time complexity of that as well.
Coming to space complexity, the idea behind space complexity is again the same that I want to calculate
the space required as a function of my input size.
Again, in this particular understanding.
Also, we will not be talking in terms of exact space, because that can actually be different with
respect to which OS you are working on, which language you are using, and other factors.
But I can still quantify that if, let's say I am given an input, what exactly will the space of with
respect to that input I will be using?
And that is what I am interested in finding out now.
Space complexity is not covered a lot and not even asked.
But I still want to make sure that I explain you this as well in very much deep.
The reason is twofold.
First is that yes, it is asked many times in algorithm, in interviews, as well as in online assessments.
Second is that being a good software developer, you should have an idea about space complexity as well.
Like it helps you to actually write make a lot better softwares okay, which are optimized and also
help you to understand that different coding practices right.
When we are actually optimizing on something.
Let's say if this algorithm uses a less space, what benefit that will have, how it will help you to
even avoid bottlenecks as well.
Okay, so let's get started.
Now I will be explaining you space complexity with a very easy example.
You can just think of your operating system like let's say you will be watching this video also in some
either on your Android phone or your laptop or somewhere.
Right?
So first let us see what space complexity comprises of.
So space complexity one second.
Yeah.
Space complexity.
Is actually the space required for input.
Space plus the auxiliary space.
Right.
Great.
So now let me actually explain them one by one to you.
First thing is the definition so required as a function of input size, something which we have already
understood with respect to time.
A lot deep I guess.
Now coming to space.
Okay.
The very first thing is the input space.
Now what do I mean by input space is let's say you have written an algorithm to sort an array.
Right.
So you are sorting an array.
Bubble sort.
Insertion sort.
You will be for that particular algorithm taking in some input.
Right.
So I will be giving you a list or I will be giving you something let's say.
So we are going to study like tomorrow.
I can give you a linked list as well to sort.
So that should be fine.
You will be taking that thing into input, right?
So that is some space we have to have to actually consider.
It is not something which you can take for free, because if you have written an algorithm, of course
you are going to take in that space and you are going to take in that input.
You cannot say that, okay, hey, I am not taking any input.
The intuitive example of this, what I can give you is you can consider your operating system.
Okay.
Let's say if you have a laptop which is having one TB.
Now normally when you buy a laptop in from that one TB, around 980 GB I think comes useful.
And then in that as well there is around 100 GB of something let's say used by your OS, right.
So windows, Mac, any Linux even uh, let's take 50 as a very conservative measure.
Okay.
Maybe less than that.
That is not the point.
Now this 50 GB right?
50 GB not TB.
My bad.
Yeah.
So this 50 GB right.
This is something which your operating system is taking.
And let's assume that you are just using an operating system only.
Now you cannot say now I will be saving this space.
I will not install anything.
Well, then, how are you going to use it?
In a very parallel manner.
If you have written an algorithm to sort an array, how are you going to sort?
If you are not taking the input?
Okay.
So that is not something which you will be optimizing on.
No you cannot.
Like you will be making sure you take the input.
And always remember many people think that space complexity is just auxiliary space, something which
you are going to discuss in just a minute.
It is not just the auxiliary space, it is the input space as well.
The hard drive in your PC is actually also having the space of operating system that is required.
You cannot avoid that, but that doesn't mean that you will not count it.
Okay, so I hope this intuitive example is a lot clear input space is considered.
So if you have written an array to sort that sorting will also consider the input which you are taking
okay.
Okay.
So that's the very first thing.
Second thing is the auxiliary space okay.
Now coming to auxiliary space this is actually the extra space which you are using in your algorithm.
Now we saw that in algorithms such as bubble sort, insertion sort, we were actually not using any
of these.
Auxiliary space.
Right.
Bubble sort.
Insertion sort.
Now many of you might think that we were using some space like I was defining different, different
variables.
Right.
So one second.
Yeah.
So that should be fine.
Yeah.
So you will see that here we are defining this n right.
So how are you saying that we are not using space.
Well the reason for that is this n which you are defining right.
That is again a constant space that is very less in consideration with, I would say, your overall
space which you are using.
The way you can think of it is like if you are creating a new folder in your OS, you don't consider
that as a space, right?
That anyway, we are creating a it doesn't have any significant in a very similar way.
These constants which you create.
Right.
You are going to create them.
Doesn't matter if the input size is just 110 100 billion.
And with respect to that, this space will just be insignificant.
Okay.
So again, you have to understand one thing we don't consider.
Let me write this as well okay.
One second.
Yeah.
So we don't consider.
Variables created.
As a extra space.
As an extra space.
Now here I just mean by variables okay.
Like these small variables which you are creating let's say I j k middle all these any way you are going
to create.
Right.
And they are insignificant.
They are not dependent on the input size.
If you are tomorrow getting an array of 100 or let's say a thousand, you are going to create the same
variables.
Plus there are some constant space, right?
Let's say in Python I know that around 28 byte is something which is initially just given to a variable
in C plus plus.
Normally four byte is there for integer and it is different based on the overall type.
Now with that understanding you have to make sure just like in time complexity, anything which you
are considering extra in auxiliary space that should depend on your input size.
Now a very good example of that algorithm which actually gets affected by this is your merge.
If you remember we used the merge algorithm, right.
So we where we merge two sorted arrays.
Now the way we did it in merge sort as well as a separate question was we actually defined, we actually
defined a new array which was having all the elements of original size.
So the size of that array, size of that answer or extra array where we were sort we were where we were
adding the sorted elements was dependent on my input size.
So if tomorrow let's say I am just saying that sorted array okay.
This was actually dependent on your input size.
Dependent on input size.
And now because this is dependent this is something actually which we care about.
Like this is actually going to add to your auxiliary space the space complexity right.
In bubble sort and insertion sort for that particular reason the space required is actually o one.
It's constant.
Whereas n merge sort you can think space required is o n because you're going to actually create an
extra array which will be having the space or the size of your input array equal to your input array.
Right.
So that's the reason we take that in auxiliary space and not those small small variables.
Okay great.
So I hope this is clear as well.
Everyone these are the two things which you will be considering.
There is one more point which I would like to explain you.
Okay, one more point.
And always remember that auxiliary space does finally become something which we have to worry about.
This is giving us major tension input spaces.
And again, not in our hands.
Right?
We cannot control the input space.
The next thing which we which I want to explain you to, is that at any given point when we talk about
space, right.
So let's say if this is the space which you are using and this is the time again, we are just consider
or have an effect with the maximum space which you are using at a time.
Okay.
So let us say you are using some space and that peaked at this particular point.
Then for your particular algorithm you are going to say that this is your space complexity, right?
How can I explain you this intuitively is that let's say you buy a new phone.
Okay.
In that phone.
In that phone you first install something.
Okay.
Let's say eight GB is your size of your phone, right?
Eight GB we can just assume let's say you install something for two GB, then you install something
for two GB more, but then you delete both of them, then you delete both of them.
Delete four GB.
Right.
Then you install something of six GB.
Now in this.
Finally, if you will see, I can say that this is plus plus this is negative.
This is plus.
The thing which I want you to understand is that you are not going to say that your overall space complexity
in this is ten GB by adding all these plus one, right?
The reason is that if you have to repeat these steps, you will be requiring just six GB of space,
right?
Because that is where your space peaked in your hard drive in your computer.
Also, if you are adding some movies and let's say after watching, if you are deleting them, you don't
count them in your overall memory.
Occupied.
Right?
You just say that.
Okay.
The.
At this point, let's say some 100 GB is occupied out of 200 GB.
So that is what your space overall complexity is.
If you added something and you have removed something that doesn't count, right, that is not something
which you are going to consider, because we always make sure that we are just considering the peak
space which is taken peak space, and that is something which we even do.
Right.
If in our PC we have, we added something, let's say in your PC up till now you must have added maybe
if, let's say it's a one TB PC, you might have added three four TB of data and deleted it over time.
But then again it never peaked above one TB.
That is what your overall space required or space complexity is for your all the actions in your PC.
Okay, so always remember this that we need to always worry about the maximum space which is required
during the full algorithm run.
We don't worry about the space which is going to get taken initially.
Sorry intuitive intermediately the space which is taken intermediately and then freed up right.
On that note, let me just show you an example as well.
So just let me show you.
Yeah great.
On that note let's say if I have n is equals to say some 10,000.
And I write this loop while I less than equals to n okay.
And what I'm doing is I'm just creating this variable a is equal to five a plus equals to one.
Then in this particular process, in this particular process, we are still using maximum space, which
is going to be 28 I guess is allotted in Python in C plus.
Plus that is four bytes for a particular integer.
The reason is that this variable has a scope.
It gets created, it gets created inside and then get destroyed.
So I'm not saying I'm not going to say that.
Hey, towards the end I will be using 28,000 of this, uh, 22, 80,000.
Rather not it was 10,000.
So I'm not going to say that I'm going to use two 80,000 space, two 80,000 bytes.
No, because this get created and this gets destroyed.
So the overall peak will actually be going to be something like this.
Only second.
Yeah it's going to be four bytes okay.
So that is what my space complexity of course it's a single variable.
But yeah that is what I would say that my space complexity is going to be if I am considering this as
a variable, I am not going to say that it is 22 80,000.
The reason is that it gets created, it gets destroyed.
So at any particular point it is not using more than 28 bytes in my PC.
If you are not able to remember what 28 bytes is, let me just quickly show you here.
Let me create a new file.
So space complexity here I am using the Jupyter notebook should be fine.
I will be sharing these to you.
Please you.
This can be also opened in Visual Studio Code so it should be fine.
Right.
So import SSIS.
This is something that you have already studied about in Basics of Python.
Let's say if I make a is equals to four then A is 28 right?
Different based on compiler based on language.
But yeah I hope you get the overall idea.
Okay, so we are just basically making sure that we are considering the peak.
Now this is how you have to calculate the space complexity.
And on that matter, I am pretty sure that for the algorithms, the iterative algorithm which we have
done, you understand that they have a one space complexity if you are not making any new list or array
or any other data structure based on the input.
Okay, so yeah, that's the overall idea behind the space space complexity.
Please make sure that you understand.
And always remember that these two are the major things which are considered input space and auxiliary
space.
And also remember this with the example, the intuitive example which I have given you how just the
peak is considered.
Okay, how I am just actually worried about the auxiliary space majorly because input is not in my hand.
But yes, again, that is something which I'm gonna give to the final output.
So if for example, just the last example, if, let's say tomorrow I have a laptop, a window, laptop,
I'm going to say that, hey, out of one TB, around 200 GB it uses for its process, and some ten GB
I am using for my processes.
So 210 GB is the space complexity, right?
So you have to consider the windows part as well.
That's the overall idea.
Okay cool.
Then everyone I hope this is clear.
Now let's meet in the next video where we are going to learn about learn more about space complexity
and also going to solve it for few algorithm which we have done.
Thank you.