What is space complexity?
Space complexity refers to the amount of memory space an algorithm uses in order to complete its execution. It describes how much space is required in relation to the input size.
The calculation of space complexity considers both the additional space the algorithm uses for its operation, such as variables, constants, pointers, and so on, and the space used to store the input values.
Space complexity is often expressed using the Big O notation, similar to time complexity.
What is Auxiliary Space?
Auxiliary space is the temporary space required by an algorithm during its execution. It includes all variables, constants, data structures, etc. used during execution apart from the space used for the input values.
Space Complexity vs Auxiliary Space
As I said, auxiliary space refers to the space used by an algorithm apart from the space used for input values. Space complexity refers to that kind of space together with the space consumed for the input values.
Therefore, we can say that the space complexity is the combination of the auxiliary space and the space used for input values.
Space complexity = Auxiliary Space + Space used for input values
Calculating Space Complexity
Here’s a step-by-step guide to help to help you determine the space complexity of an algorithm.
- Identify all variables and data structures used: Identify both input variables and any additional variables or data structures required for execution.
- Determine the space taken by each variable and data structure: Assign 1 unit of space to each element in data structures and to each variable holding a simple value. Determine how much space they use based on input size.
- Calculate the auxiliary space: Sum up all the space used by the temporary variables and data structures that are not part of the input.
- Sum up the total space: Add the space used for input values to auxiliary space. This gives you the space complexity.
- Express in asymptotic notation: Use Big O notation to express the space complexity, focusing on the dominant terms.
As an example, let’s calculate the space complexity of the following algorithm, which is intended to return two numbers in an array of numbers which together add up to a certain target value:
Let’s consider the worst-case analysis for this algorithm.
Firstly, let’s identify the variables and data structures used. For the input values, we have the nums parameter, which is an array of numbers, and a target parameter which holds a single number. For the auxiliary space, we have two variables: numSet, which holds a set of numbers, and i, which references the current index of the nums array.
Then, for the second step, we have to determine the space taken by each variable and data structure by assigning one to each element used. We will assume that the input nums has size (length) n. nums will take n units of space as it has n elements, while target takes only one unit of space. numSet gets a new number on each iteration of the loop, and it will have n elements at the end in the worst case, while i holds only a single number at a time, thus it takes up one unit of space.
The auxiliary space will then be the sum of the space taken up by numSet and i, which is n + 1, which can be expressed as O(n). The space required for the input values is the sum of the space used by nums and target, which is n + 1 and can be expressed as O(n).
The space complexity is the sum of the auxiliary space and the space used for the inputs, so we would have n + 1 + n + 1 = 2n + 2. After removing the non-dominant terms, we express it as O(n), which means that the space used grows linearly with the input size, i.e. when n increases by one, the space required increases by a constant amount.
Another example
As another example, let’s calculate the space complexity of an algorithm that calculates the sum of elements in an array.
For the auxiliary space, we only use the variable sum. For the input, we only use arr, which is an array of numbers of length n. The auxiliary space is constant as only one integer is used regardless of what n is. The space taken up by arr is proportional to n.
Therefore, the space complexity is O(n), while the auxiliary space complexity is O(1).
Notice that the space complexity and auxiliary space are not always the same, and which one you’ll consider depends on your case.
A Recursive Example
This function calculates the factorial of a given number.
When you calculate the factorial of a number n using recursion, the function keeps calling itself until it reaches the base case (usually when n = 1).
Each call to the function creates a new instance of the variable n on the call stack. Since the function calls itself n times, you end up with n instances of n on the stack.
Therefore, the complexity of this algorithm is O(n), which means that every time n increases by one, an extra unit of space is needed, i.e. the function’s space usage grows linearly (or proportionally) with the input size n.
Why should you care about space complexity?
Understanding space complexity is essential for any programmer to optimize the algorithms they build. By analyzing algorithms and determining their space complexity, you can come up with optimizations that improve the resource management, performance, scalability, and overall efficiency of the program.
Keep in mind that there may be trade-offs between space and time complexity, and which one you’ll prioritize depends on your situation. For example, in scenarios with limited memory resources, such as embedded systems or mobile applications, you might prefer algorithms that use less memory, even though they may take more time to execute.
Donate
Did you like this article? If you did, please consider buying me a coffee.
