Space complexity, as I mentioned in this article, is the total space needed to execute an algorithm. We use memory to store some data. The main part of memory consumption in algorithms comes from the use of variables.
In simple words if we have a function that takes some data as an input Big O and space complexity will be about how much memory will our function use up to complete as the input grows.
In the case of high time complexity, the algorithm will simply take a long time to execute. We will just have to wait a long time for its implementation. In the case of space complexity, this is important because the excess memory used by the computer will not allow such an algorithm to run. Computer will just fall asleep.
If you want more about what complexity generally means again i’m point out this article. For now let’s move on to the examples.
function loopSum(arr) {
let sum = 0;
for (let i = 0; i < arr.length; i++ ) {
sum += arr[i]
}
return sum;
}The function above uses two variables (sum and i), so it only uses two units of memory. Regardless of the number of overwrites in memory, there will always be only two locations for this data. Therefore, we are dealing here with constant space complexity O(1).
Another example:
function loopDouble(arr) {
let tens = [];
for (let i = 0; i < arr.length; i++) {
tens.push(10 * arr[i])
}
return tens;
}In the next example, we see the use of an array. The content of tens grows with each iteration of the loop. Strictly speaking, with each iteration, we add one number to this array. For each of these numbers you will need a new memory location. So here we have an example of O(n) complexity. Where n is the number of numbers in the array passed (through the arr parameter).
When it comes to the space complexity of individual basic language constructs, it usually looks like this:
- Most primitive values (booleans, numbers, etc.) have constant O(1) complexity.
- Character strings (strings) have O(n) complexity – n in this case is the length of the string.
- Values of reference types such as objects or arrays are also O(n) – n means the number of fields / elements.
Summary of the space complexity of algorithms
To sum up both articles about complexity and Big O notation:
We use the Big O notation to analyze the performance of algorithms.
Time complexity determines the ratio of time to the amount of data transferred to the algorithm. Space complexity – the memory used during the execution of the algorithm to the amount of transferred data.
Big O doesn’t just care about the overall trend, whether performance or memory usage is roughly equal to the amount of data, or whether it increases or decreases as data increases.
At Big O, we only consider the worst-case scenario. We do not consider constant or less significant numbers.
Monitoring space complexity is important because if the algorithm is ‘too heavy’, it will lead to overloading of the computer and thus its suspension.
PS
Again, here is the first part of this article.
If you would like to learn about functional programming you can find a summary of the most important concepts here.
Maybe you don’t know what is the abstraction in programming?
This article sums up everything what you should know about it!
More about space complexity you can find for example here.
Senior Software Engineer with over 7 years of experience and entrepreneurial background. Most often, apart from delivering good quality code on time, responsible for introducing good practices, teaching programmers and building team bonds andestablishing communication on the line of development-management. Privately Kākāpō and Wombat enthusiast, traveler and retired acrobat.