Analysing Space Complexity

Question

I have to compute the space complexity of this function:

double foo(int n){
     int i;
     double sum;
     if(n==0) return 1.0;
     else
          for(i=0;i<n;i++)
              sum+= foo(i);
     return sum 
}

What I have done:

When function is called, the activation record is created on the call stack. For $foo(n)$ let the size of AR be $x$.

• $foo(0)$ does not place any recursive calls.
• $foo(1)$ places 1 recursive call. Terminates at $foo(0)$.
• $foo(2)$ places 2 recursive calls to $foo(0)$ and $foo(1)$.
• $foo(1)$ places another recursive call. Therefore total calls placed is 2+1.
• $foo(3)$ places 3 recursive calls to $foo(0)$,$foo(1)$ and $foo(2)$. Therefore total calls placed is $3+0+1+3= 7$ recursive calls.
• $foo(4)$ places 4 recursive calls. $4+0+1+3+7= 15$.

Hence we can see that $foo$ produces calls in the pattern: 0,1,3,7,15,31,...

This shows us that $foo(n)$ produces $(2^n)-1$ recursive calls.

If we count the total no. of recursive calls made by $foo(n)$ it becomes a geometric series and evaluates to approximately $(2^n)-n$.

Hence I am getting Space complexity to be $O(2^n)$.

However several books have merely listed the answer as $O(n!)$ without giving an explanation. I just want to know where I am going wrong in my approach.

Answer 1

In my opinion you are not quite right...

During the loop, when you return from foo(i), the spaces used by the call foo(i) is released (I mean, the stack pointer is back to the previous position).

So actually foo(i) only uses 1 more AR than foo(i - 1). The space cost should be O(n).

This can be verified by running the code with foo(25) and specify a stack of size 1 MB (disable all optimizations, of course). It will return normally within several seconds, without "stackoverflow". This is a proof that it's not using O(2^n) space.