Space complexity in the call stack

Question

I'm reading Cracking the Coding Interview, and in the Big O section of the book we are posed with this piece of code:

int pairSumSequence(int n){

    int sum = 0;
    for(int i = 0; i < n; i++){
        sum += pairSum(i, i + 1);
    }
    return sum;
}

int pairSum(int a, int b) {
    return a + b;
}

Now, I understand that the time complexity is of O(n), because it's clearly obvious that the time to execute increases as the size of the int n increases. But the book continues to state that:

"...However, those calls [referring to calls of pairSum] do not exist simultaneously on the call stack, so you only need O(1) space."

This is the part I do not understand. Why is the space complexity of this algorithm O(1)? What exactly does the author mean by this? At my initial analysis, I assumed that because pairSum() is being called N times those calls would be added to the call stack back-to-back and would thus occupy N space in the call stack. Thanks very much.

Answer 1

It means that the amount of space used by this algorithm is constant with respect to the input size.

Yes, the pairSum is called N times. However, it occupies O(1) space because, as the book says, no two calls are done simultaneously.

Roughly speaking, at each iteration of the loop:

1. The pairSum is called. It uses a constant amount of the stack space.

2. It returns. It doesn't occupy any stack space after that.

Thus, this algorithm uses only a fixed amount of space at any point (it doesn't depend on n).