Space complexity in data structure

Written by

Sonal Moga

Whar are Asymptotic Notations?
The Time complexity of Algorithms
Space Complexity of an Algorithm

Space Complexity of an Algorithm

As we have already discussed time complexity in detail and we are well aware of the fact that time and space complexities are the two factors that quantify the efficiency of any algorithm. Here, we will discuss Space Complexity.

Space complexity evaluates the space/memory acquired by an algorithm to run as a function of the input OR as the amount of working storage needed by an algorithm to function and return the result.

For any algorithm to function it needs storage/space for the following:

  • Inputs/ variables 
  • Program code
  • Auxiliary space required for the execution

Auxiliary space is the extra space needed by an algorithm for execution.

Space Complexity = Auxiliary Space + Input Space

Space Complexity is vital for an algorithm because when huge data (in real-time) is searched or traversed through an algorithm, quite a large amount of space is needed to hold the inputs and variables along with the code that is being run. The largest amount of space is needed to return the result after the execution of the algorithm.

Generally, we tend to ignore the space needed for variables and instructions while calculating the Space complexity. Since actual data is quite huge contrary to small array inputs that we enter while learning process. So, if we only consider the number of variables being declared and called for in an algorithm a multiple number of times will need a significant amount of space to hold it while execution. Here we have not yet considered the fact that sometimes calling another algorithm in a running algorithm can also be a case that may need a tad more space than usual.

Let us quickly glance over the space needed by different types of data type variables

These values may not show the importance of space complexity but when data is humongous it is very important to use the algorithm that is efficient in both Space & Time complexity.

 

Space complexity in data structure