# Space Complexity

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

• 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} – Abhishek Bansal Dec 24 '15 at 16:59
• 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? – D.W. Dec 31 '15 at 23:08
• 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. – Sagnik Jan 2 '16 at 11:28