in Algorithms retagged by
176 views
0 votes
0 votes
what is space complexity of an algo?

and what is the number of function calls in general?
in Algorithms retagged by
176 views

1 Answer

0 votes
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(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

1 comment

The amount of extra space required by an Algo is considered for space complexity..

By extra i mean apart from the input size..
2
2