Hey everyone, I hope you all are doing wonderful. Let's start today's DSA with Me series second article. Today we are going to talk about Space Complexity and Auxiliary Space and how they are not the same things. Yes! few people think Space Complexity and Auxiliary Space are the same. We are going to debunk that myth today. We'll also see why Auxiliary Space is a better criterion than Space Complexity to judge an algorithm.
Before starting I would like to tell you that in this article I'm going to use a few things from my previous article, What Is Time Complexity. So, if you are not familiar with time complexity and asymptotic notations then I would suggest you go and read that first.
Now let's get rock and rolling🚀
What is Space Complexity
Space complexity is the amount of total memory space(RAM space) taken by a program with respect to the input size when the program is executing.
As a beginner, we usually don't pay much attention to the space complexity as compared to the time complexity, because usually in simple programs space complexity is constant. It's Big O of 1, O(1).
Space complexity comes into play when we use data structures in our program whose size is dependent on the input size of the program. And also in the recursive programs, to store recursion calls in call stack.
Note: In Space Complexity analysis also we use the same Asymptotic Notation as in Time Complexity analysis.
Let's take a quick example of how to calculate space complexity👇
If we create an array of size n, this will require O(n) space. If we create a two-dimensional array of size n*n, this will require O(n2) space.
How to calculate Space Complexity?
Steps to calculate the Space Complexity of a program:
- List all the variables present in the program.
- Take c for variables that take constant space.
- Take n for variables whose size linearly depends upon the size of the input.
- n^2 for variables whose size is directly proportional to the square of the input size. Take the exponent of n depending upon the relation with the input size.
- Calculate the total space, you'll get an equation. The highest order of n will be the space complexity in Big O notation.
I know some of you might be scratching your head. Don't worry we'll understand this better with an example.
let’s determine the space complexity of a program that sums all integer elements in an array:
public int sumArray(int[] array) {
int size = array.length;
int sum = 0;
for (int i = 0; i < size; i++) {
sum += array[iterator];
}
return sum;
}
By following the steps stated above:
- Listing all the variables:
array – the function’s only argument – the space taken by the array is equal to 4n bytes, where n, is the length of the array. And it's multiplied by 4 because it is an integer array and the size of an int variable is 4bytes; so every array element will take 4 bytes of space and the total number of elements are n.
size – a 4 byte integer
sum – a 4 byte integer
i – a 4 byte integer
equation: 4n+c+c+c → 4n + 3c
The highest order of n in the above equation is 4n, hence the Space Complexity of the above program in Big O notation is: O(n)
What is Auxiliary Space
Auxiliary space is the extra or temporary amount of memory space taken by the program. It does not take the space taken by the input into account like space complexity.
Now let's see why Auxiliary Space is better than Space Complexity when it comes to judging algorithms.
Merge Sort, Insertion Sort, and Heap Sort all have the same Space Complexity which is O(n). However, the Auxiliary Space taken by Insertion Sort and Heap Sort is O(1), and by Merge Sort is O(n).
Through the above example, we can see that Space Complexity failed to provide a winner among the three algorithms. Whereas, the Auxiliary Space clearly presented that Insertion Sort and Heap Sort are better algorithms when it comes to space analysis.
If we take another example, the one we saw in space complexity analysis; Program to find the sum of integer array elements.
public int sumArray(int[] array) {
int size = array.length;
int sum = 0;
for (int i = 0; i < size; i++) {
sum += array[iterator];
}
return sum;
}
The Space Complexity of the above program is O(n) because it takes the input size into account. However, the Auxiliary Space Complexity of the above program is O(1) because the program doesn't take any extra space or temporary space which depends on the input.
I hope now you can clearly see the difference between Space Complexity and the Auxiliary Space.
Wrapping Up
That's all for today folks, I hope you got to learn something new today. If you got confused with all the notation parts I would recommend you to first read the Time Complexity article. In that, I have explained the Asymptotic Notation in detail.
Thanks for reading, if you like reading my articles then consider following Mudit Mishra on Hashnode, you can also connect with me on Twitter.
Follow DSA with Me series and let's help each other in learning and growing together.