Now let's explore space complexity.
We have already seen that time complexity is how the runtime increases as the input size increases.
Now, space complexity in a similar manner deals with the extra space consumed by the algorithm as the
input size increases.
So again, as the case of time complexity, space complexity is also expressed using Big-O notation
itself.
So if you say that the space complexity of an algorithm is O of one, it means that the space required
by the algorithm to run does not scale as the input size scales.
Similarly, if you have an O of n space complexity, it means that the space requirement by the algorithm
scales linearly as the input size grows.
Now this over here space complexity, let me just write it over here means how much auxiliary memory
is needed to run the algorithm.
So over here we have an interesting point.
We only deal with the auxiliary memory or extra memory, which is the space required or additional space
required only by the algorithm.
We don't consider the size of the input.
It's understood that as the input size increases to store the input, we would require more space.
But we are not going to consider that.
When we evaluate the efficiency of the algorithm, we only deal with the extra space required by the
algorithm to execute.
All right.
So that is what space complexity is about.
Now a few interesting pointers.
In some coding interview questions, you can see that we can improve the time complexity by using up
more space.
So in those cases it's a trade off between time complexity and space complexity.
In some solutions, maybe you can see that you can improve the time complexity by storing some values
in a new array, or a string, or a hash map, etc..
Right?
So in those cases there would be some space used up.
Now also remember primitives such as numbers, boolean, null, undefined, etc. all take up constant
space.
So we have got a good idea about space complexity as well.
Now let's take a look at a few techniques to simplify Big-O expressions.
So these are again things that we have discussed while we discussed the asymptotic analysis.
But over here let's just discuss it as pointers to techniques.
So the first technique is drop the constant.
So for example if you have the time complexity or the space complexity as O of 25 into n square, drop
the constant and you can say that it simplifies to o of n square.
The second pointer is drop in significant terms as n increases.
Right.
So we have seen this in the case of asymptotic analysis.
So if you see that the expression is O of n cube plus 100 n, then you can drop this because this is
a constant.
And then you can drop n because compared to n cube n is going to be insignificant.
So you can drop that.
And this simplifies to o of n cube.
Now the third point is if there are different input parameters this is something that you should remember.
You cannot drop them.
For example, if you have O of n cube plus M, you cannot drop this M because you have n cube over here.
So that's an important thing.
All right.
So why is that.
So for example there can be a scenario where n is just one but m is 10,000.
So you can see that in that case m is much bigger than n cube.
So that's why this is a possibility right.
So this is a valid possibility.
So if the input parameters are different then you cannot drop them just because one is of greater power
etc..
Like if this was n then we would have dropped it.
But because both of them are different you cannot drop them.
All right.
So these are three interesting techniques that you can keep in mind to simplify Big-O expressions.
Now let's come to the final part and let's discuss logarithms.