What is Space Complexity and How to Calculate it?

Space complexity is a measure of how efficient your code is in terms of memory used.

Space complexity analysis happens almost in the same way time complexity analysis happens, i.e. it is measured by calculating the total space taken by an algorithm with respect to the input.

Eg: Let’s take the following example:

vector<int> V;
for (int i = 0; i < N; i++) V.push_back(i)

The code snippet ends up creating a vector of size N. So, space complexity of the code is O(n).

Eg: Let’s take another example. Let’s say we need to create a 2-D array of size n*n.

The space complexity in this case would be O(n2 ) .

Similar to Space complexity there is another concept called Auxiliary Space.

Auxiliary space is the extra space used by the algorithm apart from the input space.

Eg: The following is the code for calculating the sum of an input array.

Int sum( int arr[] , int n)
{
	int sum=0;
	for (int i=0 ; i< n ; i++)
	{
		sum+=arr[i];
      }
      return sum;
}

In the above algorithm apart from the input array we only declare one variable ‘sum’. 
Therefore for the above algorithm , 

• Auxiliary Space = O(1)
• Space complexity = O(n)

Difference between Time Complexity and Space Complexity:

Now that we know what time complexity and space complexity is, and how to calculate them, Let's discuss some key differences between them.

Space Complexity Cheat Sheet

Here’s a list of some famous algorithms and their space complexities.