Skip to main content

Space Complexity

Space complexity is a measure of the amount of working storage an algorithm needs. It is a measure of the amount of memory space an algorithm needs to solve a problem as a function of the size of the input to the problem. It is the amount of memory space required by the algorithm to execute in its life cycle.

Why is Space Complexity important?​

Space complexity is important because the memory that is allocated to the program is limited. If the program uses more memory than the available memory, the program will crash. Therefore, it is important to know the space complexity of the algorithm.

How to calculate Space Complexity?​

Space complexity is calculated by counting the amount of memory space used by the algorithm. It is calculated by counting the amount of memory space used by the algorithm as a function of the size of the input to the problem.

Example​

Space Complexity
function sumOfN(n) {
let sum = 0;
for (let i = 1; i <= n; i++) {
sum += i;
}
return sum;
}

In the above example, the space complexity of the algorithm is O(1) because the algorithm uses a constant amount of memory space.

Example of Space Complexity​

  1. Write a program to fine maximum and minimum element in an array.
Written by @Ajay-Dhangar
function findMaxMin(arr) {
let max = arr[0];
let min = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
return { max, min };
}

const arr = [2, 5, 1, 20, 10];
console.log(findMaxMin(arr)); // { max: 20, min: 1 }

In the above example, the space complexity of the algorithm is O(1) because the algorithm uses a constant amount of memory space.

Explanation: In the above example, we are finding the maximum and minimum element in an array. We are using two variables max and min to store the maximum and minimum element in the array. We are using a constant amount of memory space to store the maximum and minimum element in the array. Therefore, the space complexity of the algorithm is O(1).

Complexity Analysis

Farmula to calculate Space Complexity

Space Complexity = Constant Space + Auxiliary Space

Constant Space: The amount of space used by the algorithm that is not dependent on the size of the input to the problem. It is a constant amount of memory space used by the algorithm.

Auxiliary Space: The amount of space used by the algorithm that is dependent on the size of the input to the problem. It is a variable amount of memory space used by the algorithm.

Space Complexity
Space Complexity = O(1) + O(n) = O(n)

For Example:

Space Complexity
function sumOfN(n) {
let sum = 0; // Constant Space (O(1))
for (let i = 1; i <= n; i++) {
sum += i; // Auxiliary Space (O(n))
}
return sum;
}

In the above example, the space complexity of the algorithm is O(1) + O(n) = O(n).

Conclusion​

Space complexity is a measure of the amount of working storage an algorithm needs. It is a measure of the amount of memory space an algorithm needs to solve a problem as a function of the size of the input to the problem. It is the amount of memory space required by the algorithm to execute in its life cycle.