Space Complexity with Examples

What is Auxiliary Space? 

Auxiliary means extra space used by an algorithm, like arrays, pointers, etc.

When comparing sorting algorithms, it is better to reference Auxiliary Space. Why? In the case of space complexity, all of the sorting algorithms that an array consists of O(n) space complexity given the input size. That being said, auxiliary space for insertion and heap sort uses O(1) auxiliary space, while merge sort uses O(n) auxiliary space given the conditions required to create temporary subarrays.

The best algorithm should have the least space complexity. The lesser the space used, the faster it executes as if a program takes up a lot of memory space, the compiler will not let you run it.

Recommended topic, kth largest element in an array

Space Complexity Examples

Example1:

public static void main(String[] args) {
   int a=1,b=2;
   int c=a+b;

   System.out.println(c);

}

Output

3

Three integer variables are used in the above example. Depending on the compiler, the integer data type can be 2 or 4 bytes in size. Let'sLet's say the size is four bytes. As a result, the example mentioned above takes up 4 * 3 = 12 bytes in total. There is no need for additional space because no additional variables are required.

Therefore, space complexity is O(1), or constant.

Example2:

public static void main(String[] args) {

   int n=4;
   int arr[]=new int[] {1,2,3,4};
   for(int i=0;i<n;i++)
   {
       System.out.println(arr[i]);
   }
}

Output

1
2
3
4

The array in the code above is made up of n integer elements. As a result, the array takes up 4 * n of space. There are also integer variables like n, i. The total space occupied by the program is 4n + 8 bytes, assuming each variable is 4 bytes. The space complexity is O(n), or linear because the largest order of n in the equation 4n + 8 is n.

For a 2D array, the space complexity is O(n*n).

Read More - Time Complexity of Sorting Algorithms

Frequently Asked Questions

Why Space Complexity plays a crucial role in programming?

It defines the amount of space the algorithm requires as per the input size. The lesser the space used, the faster it executes.

State the difference between space and auxiliary space?

Auxiliary is the extra space used by an algorithm, whereas space complexity includes both auxiliary space and the space taken by the input.

See more, euclid gcd algorithm

Key Takeaways

In this blog, we have covered the following points:

• What is the difference between the space and auxiliary space?
• What is the need to find the space complexity?
• O(1) - Constant Space Complexity occurs when the program doesn't contain loops, recursive, or calls to other functions.
• O(n) - Linear space complexity occurs when the program includes loops.

Also, don’t forget to practice the wide variety of DSA problems frequently asked in interview rounds readily available on Code360 

Check out this problem - Longest Subarray With Sum K 

Happy coding!!