Space Complexity measures the total amount of memory that an algorithm or operation needs to run according to its input size.
Space Complexity is a parallel concept to Time Complexity. We express space complexity measurements using the Big-O notation, following the same guidelines like we do for time complexity.
Now let's learn how to compute space complexity by taking a few examples:
Constant Space Complexity:
function sum(a, b) {
let sum = a + b;
return sum;
}
In the example above, we use 3 number variables: a and b, which are input variables and sum, which is an auxiliary variable.
And because the space requirement is fixed (3 number variables), hence it is called Constant Space Complexity and is noted with O(1).
Linear Space Complexity:
function generate(n) {
let numbers = [];
for (let i = 0; i < n; i++) {
numbers.push(i);
}
return numbers;
}
In the example above, we use an auxiliary array numbers which is populated with n numbers.
Since the total space requirement is n numbers, the Space Complexity is increasing linearly with the increase in the input value n, hence it is called as Linear Space Complexity and is noted with O(n).
Quadratic Space Complexity:
function generate(n) {
let numbers = [];
for (let i = 0; i < n; i++) {
numbers.push([]);
for (let j = 0; j < n; j++) {
numbers[i].push(j);
}
}
return numbers;
}
In the example above, we use an auxiliary 2D array numbers of n rows and n columns.
Since the total space requirement is n^2 numbers, the Space Complexity is directly proportional to the squared of the input value n, hence it is called as Quadratic Space Complexity and is noted with O(n^2).
Extra/Auxiliary Space:
Sometimes Extra/Auxiliary Space is confused with Space Complexity. But Auxiliary Space is the extra space or the temporary space used by the algorithm during it's execution (without taking the input values into account).
Space Complexity = Auxiliary Space + Input space
Let's see some examples:
function sum(arr) {
let sum = 0;
for(let num of arr) {
sum += num;
}
return sum;
}
In the example above, we have an input array arr. If we denote its length by n, the Input Space is O(n).
However, we use only 2 auxiliary variables sum and num, so the Extra Space is O(1).
The core challenge of understanding space complexity lies in identifying how much additional memory an algorithm requires relative to its input size. This is significant in scenarios where memory resources are limited, such as embedded systems or large-scale data processing.
Common applications include optimizing algorithms for better performance and ensuring that programs run efficiently within the available memory constraints.
Potential pitfalls include confusing space complexity with time complexity and not accounting for all auxiliary space used by the algorithm.
To solve problems related to space complexity, follow these steps:
Let's discuss different approaches with examples:
Consider a naive solution where we do not optimize for space. For example, creating multiple copies of data unnecessarily can lead to higher space complexity.
Optimized solutions aim to reduce the auxiliary space used. For instance, using in-place algorithms where possible can significantly reduce space complexity.
Let's break down the algorithm for calculating the sum of an array with minimal space complexity:
#include <iostream>
#include <vector>
using namespace std;
// Function to calculate the sum of elements in an array
int sum(const vector<int>& arr) {
int sum = 0; // Auxiliary variable
for (int num : arr) {
sum += num; // Accumulate the sum
}
return sum;
}
int main() {
vector<int> arr = {1, 2, 3, 4, 5};
cout << "Sum: " << sum(arr) << endl;
return 0;
}
Here is the C++ implementation of the sum function:
#include <iostream>
#include <vector>
using namespace std;
// Function to calculate the sum of elements in an array
int sum(const vector<int>& arr) {
int sum = 0; // Auxiliary variable
for (int num : arr) {
sum += num; // Accumulate the sum
}
return sum;
}
int main() {
vector<int> arr = {1, 2, 3, 4, 5};
cout << "Sum: " << sum(arr) << endl;
return 0;
}
The time complexity of the sum function is O(n) because it iterates through the array once. The space complexity is O(1) for the auxiliary variable sum, plus O(n) for the input array, resulting in a total space complexity of O(n).
Consider edge cases such as an empty array or an array with a single element. The algorithm should handle these gracefully:
#include <iostream>
#include <vector>
using namespace std;
// Function to calculate the sum of elements in an array
int sum(const vector<int>& arr) {
int sum = 0; // Auxiliary variable
for (int num : arr) {
sum += num; // Accumulate the sum
}
return sum;
}
int main() {
vector<int> arr1 = {};
vector<int> arr2 = {10};
cout << "Sum of empty array: " << sum(arr1) << endl;
cout << "Sum of single element array: " << sum(arr2) << endl;
return 0;
}
To test the solution comprehensively, include a variety of test cases:
Using testing frameworks like Google Test can help automate and manage these tests effectively.
When approaching such problems, consider the following tips:
Understanding space complexity is crucial for writing efficient algorithms, especially in memory-constrained environments. By analyzing and optimizing space complexity, you can ensure that your programs run efficiently and effectively.
For further reading and practice problems, consider the following resources: