CODEWITHSUNDEEP
algorithm
Giancarlo Manuel Guerra Salvá
Giancarlo Manuel Guerra Salvá

Reputation: 1942

Space complexity in the call stack

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.

Upvotes: 4

Views: 2338

Answers (2)

navaneeth mohan
navaneeth mohan

Reputation: 121

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.

Had this been a recursive algorithm then you would have been correct. When you see a for loop you can be quite certain that it is an iterative algorithm. Meaning, instructions are pushed and popped from the call-stack before pushing the next instruction.

Upvotes: 0

kraskevich
kraskevich

Reputation: 18566

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).

Upvotes: 7

Related Questions