Space complexity of a given recursive program

Question

Consider the following C-function:

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

The space complexity of the above function is

1)  O(1)
2)  O(n)
3)  O(n!)
4)  O(n^n)

in the above question, according to me, answer should be (2) but answer is given as (3) option. Although it is recursive function but stack will never have more than O(n) stack depth. Can anyone explain me why is this answer (3) and where am I thinking wrong?

Answer 1

If You needed time complexity then it is certainly not O(N!) as many suggest but way less then that it is O(2^N).

Proof:-

T(N) = T(N-1) + T(N-2) + T(N-3) + T(N-4)........T(1)

moreover by above formula

T(N-1) = T(N-2) + T(N-3)...... T(1)

hence T(N) = T(N-1) + T(N-1) = 2*T(N-1)

solving above gives T(N) = O(2^N)

Whereas if you needed space complexity then for recursive function space complexity is calculated by the amount of stack space at max occupied by it at a moment and that in this case cannot exceed of O(N)

But in any case the answer is not O(N!) because that many computations are not done at all so how can stack occupy that much space.

Note:- Try to run the function for n = 20 if it doesnt cause memory overflow then answer given in text will be 20! which is larger than any memory but i think it will run in O(2^20) time without any stack overflow.

Answer 2

Space complexity is O(N). at any given time the space used is limited to: N*sizeof_function_call_which_is_a_constant.

Answer 3

Think of it like this:

To calculate foo(n) . The program have to calculate: foo(0)+foo(1)+foo(2) ... foo(n-1):

Similarly for foo(n-1). The program have to recursively calculate: foo(0) + foo(1) + ... foo(n-2).

Basically you will have O(foo(n)) = n! + (n-1)! + (n-2)! + ... 1! = O(n!).

Hope this is clear.