2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What's your unit; bits or (arbitrary-size) words? $\endgroup$ – Raphael Jul 22 '15 at 10:59
  • $\begingroup$ The time complexity is $\Theta(2^n)$. $\endgroup$ – Yuval Filmus Jul 22 '15 at 13:08
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You are right, the recursive calls are not at the same time, thus the space is linear (at the worst moment foo(n) is running foo(n-1) which is running .. foo(1) : n functions foo are in the stack) $\endgroup$ – François Jul 21 '15 at 13:28
  • $\begingroup$ Thank you. Should have used the recursion tree and call stack method. $\endgroup$ – Sagnik Jul 22 '15 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.