Space complexity is a parallel concept to time complexity. If we need to create an array of size n, this will require O(n) space.
If we need a two-dimensional array of size nxn. this will require O(n2) space.
Stack space in recursive calls counts, too. For example, code like this would take 0( n ) time and O(n ) space.
int sum(int n) { /* Ex 1.*/
if (n<=0) {
return 0;
}
return n + sum(n-1);
}
Each call adds a level to the stack.
1 sum(4)
2 --sum(3)
3 ------sum(2)
4 --------sum(1)
5 ------------sum(0)
Each of these calls is added to the call stack and takes up actual memory.
However, just because you have n calls total doesn't mean it takes O(n) space. Consider the below function, which adds adjacent elements between O and n:
int pairSumSequence(int n) { /* Ex 2.*/
int Sum = 0;
for (int i a=0; i < n; i++) {
sum +=pairsum(i, i + 1);
}
return sum;
int pairSum(int a, int b) {
return a + b;
}
There will be roughly O ( n ) calls to pairSum. However, those calls do not exist simultaneously on the call stack, so you only need 0(1) space.
Source: Cracking the coding interview by Gayle McDowell
