Space Complexity in Algorithm
Arya Krishna
Posted on May 4, 2022
When we talk about space complexity, remember that we are talking about the space that an algorithm takes up as the size of the input increases. We are indicating auxillary space complexity here means we are just focusing on what happens inside the algorithm.
Things to remember in Space Complexity -
- Primitive things like booleans numbers, undefined, null and JavaScript are constant space.
- Strings require
o(n)
space where n is the length of the string. For example a string with 10 characters take more space than a single character string.
Let's see an example -
Determine the space complexity of the following -
Determine the space complexity for the following function
function sum(arr) {
let total = 0;
for (let i = 1; i < arr.length; i++) {
total+= arr[i];
}
return total;
}
So this function called sum, it takes an array and it just sums all the items in the array. We have a variable total
that starts at 0. Then we have the loop that goes from 0 to the end of the array and we're just adding in the value
of each item in the array to the total variable and then we return it at the end. Remember, it is space that we are considering and not time. No matter what the array length is, we have one variable called total one number and then we're
looping through and we have a second declaration inside the For loop. Thus we have only these two variables and they exist no matter what. We're adding to the total variable, but we're not making a new variable. So that really just means we have constant space of one space.
Posted on May 4, 2022
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.