Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Space Complexity?
3.
What is Auxiliary Space? 
4.
Space Complexity Examples
4.1.
Example1:
4.2.
Example2:
5.
Frequently Asked Questions
5.1.
Why Space Complexity plays a crucial role in programming?
5.2.
State the difference between space and auxiliary space?
6.
Key Takeaways
Last Updated: May 23, 2024

Space Complexity with Examples

Author Soumya Agrawal
2 upvotes
gp-icon
Competitive programming
Free guided path
16 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

 

The two parameters which should be considered while thinking the approach for any problem are Time and Space Complexity. 

 

What is Space Complexity?

Space complexity is the amount of space the algorithm takes for the input size. It includes both auxiliary space and the space taken by the input.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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!!

 

Previous article
Time Complexity
Next article
Amortized Time Complexity in Data Structures
Guided path
Free
gridgp-icon
Competitive programming
16 chapters
217+ Problems
gp-badge
Earn badges and level up
Live masterclass