Beside time complexity, space complexity is another measurement to determine if you code is a good one. When we talk about time complexity, we are referring to the speed of your algorithm, or in other words, how many operations does it cost. For space complexity, it is about the memory your algorithm needs to execute.
1. What is Space Complexity
Space complexity is a measure of the amount of working storage an algorithm needs.
That means how much memory, in the worst case, is needed at any point in the algorithm. As with time complexity, we're mostly concerned with how the space needs grow, in big O terms, as the size N of the input problem grows.
When a program executes, the are two ways to remember things: the heap and the stack. The heap is usually where the computers store variables the we assign values to and the stack is usually where we keep tracks of the function calls.
2. Space Complexity Causes
So, what causes space complexity? Below are the causes:
- Variables
- Data Structures
- Function Call
- Allocations
We will understand more the causes by looking at the example below:
function Func1(array) {
for (let i = 0; i < array.length; i++) { // O(1) for let i = 0
console.log('hello');
}
}
Func1([1,2,3,4,5]); //Space Complexity: O(1)When we talk about space complexity, we talk about additional space needed to execute the function. Therefore, we don't care about space taken up by the input. For the above function, we don't really add anymore memory beside adding a variable i = 0 in a for loop. So, the above function costs O(1) space complexity.
Let's consider another function below:
function Func2(array) {
let anotherArray = [];
for (let i = 0; i < array.length; i++) { // O(1) for let i = 0
anotherArray[i] = 'Hello'; // O(n) for adding value to anotherArray n times (n is size of array)
}
return anotherArray;
}
Func2([1,2,3,4,5]); //Space complexity is O(n)In the above function, we create a new data structure which is an array. Then, we add value to the new array n times where n is the size of the input. So, the above function costs O(n) space complexity.