1
$\begingroup$

This particular code is written in C.

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

The Question given is: Calculate the space complexity of the following function.

My Solution: foo(x) never occupies more than x cells on the call stack, so the auxiliary space complexity for the function is: O(n) for n inputs.

However the answer to this problem was given as O(n!) by a book and O(2$^n$) by our professor (he didn't solve it).

I have two questions here:

  1. Is my calculation of the auxiliary space complexity correct? If not why?
  2. What is the total space complexity? Is it still O(n)?

Edit: I have asked this question before on cs.stackexchange itself but I still cannot fathom this mystery. The link to the previous question is:

Analysing Space Complexity

$\endgroup$
  • 2
    $\begingroup$ According to me you are correct, space complexity should be O(n) since the maximum depth of recursion is n, but time complexity should be O(2^n) because T(n) = Sum(T(i)) {i=0 to n-1} $\endgroup$ – Abhishek Bansal Dec 24 '15 at 16:59
  • $\begingroup$ You already got an answer here that says the space complexity is $O(n)$. What more of an answer are you expecting? What is your specific uncertainty/confusion? We discourage "please check whether my answer is correct" questions, as they're unlikely to be useful to anyone else. Is there any reason not to close this as a dup of that one? $\endgroup$ – D.W. Dec 31 '15 at 23:08
  • $\begingroup$ I have added a query about the total space complexity as well. I guess if you want to close it as a duplicate my hands are tied, but if you observe carefully the tone of the two questions are quite different. $\endgroup$ – Sagnik Jan 2 '16 at 11:28

Your Answer

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

Browse other questions tagged or ask your own question.