By extra i mean apart from the input size..

Dark Mode

184 views

0 votes

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(n^{2}) 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