Space complexity

Space Complexity is a concept in theoretical computer science, specifically Complexity Theory, which is used to measure and describe the efficiency of an algorithm in terms of the amount of memory they will require to store the information they need. Algorithms, when implemented in computer programs, require two main resources when the program is executed: time and memory. Memory, particularly, may be expensive in large quantities. Therefore it is often desirable to make modifications to an algorithm so as to reduce its space complexity, that is, make it use less memory when run.

Space Complexity and Input Size

As with time complexity, space complexity is usually given in terms of the input size, using Big-O notation. Usually, the input size is given as a number [math]\displaystyle{ n }[/math] that refers to an amount of elements that need to be considered to solve a problem. The space complexity is then often given as a function that gets larger as [math]\displaystyle{ n }[/math] increases. This function indicates how quickly the memory requirement grows when [math]\displaystyle{ n }[/math] is very large.

Auxiliary Space Complexity refers to the amount of storage space that the algorithm will use besides the storage space which is already used for the input data. As the input data for any algorithm will have to be stored in memory, it is often more important to know whether the algorithm can operate "in place", i.e. without a need for memory that will grow as [math]\displaystyle{ n }[/math] gets large.

Relationship With Time Complexity

The other resource that algorithms consume is time. The so-called time complexity of an algorithm is measured in the same way and is more commonly taught first in courses covering algorithms. It is worth noting that there is a relationship between the auxiliary space complexity of an algorithm and its time complexity: since the former measures the amount of data that is created after the algorithm begins, the time complexity is always greater than the auxiliary space complexity.