Calculating the space complexity of a C-function?

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:

(a) O(1) (b) O(n) (c) O(n!) (d) O(n^n)

What I've done is calculating the recurrence relation for the above code but I'm still not able to solve that recurrence. I know this is not home work related site. But any help would be appreciated.

This is my recurrence.

T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4) +........+ T(1)+ S

Where S is some constant.

Answer 1

That would depend on whether you're talking about stack, or heap space complexity.

For the heap, it's O(1) or O(0) since you're using no heap memory. (aside from the basic system/program overhead)

For the stack, it's O(n). This is because the recursion gets up the N levels deep.

The deepest point is:

foo(n)
    foo(n - 1)
        foo(n - 2)

        ...

        foo(0)

Answer 2

Space complexity describes how much space your program needs. Since foo does not declare arrays, each level requires O(1) space. Now all you need to do is to figure out how many nested levels can be active at the most at any given time.

Edit: ...so much for letting you figure out the solution for yourself :)

Answer 3

You don't explain how you derived your recurrence relation. I would do it like this:

1. If n == 0, then foo uses constant space (there is no recursion).
2. If n > 1, then foo recurses once for each i from 0 to n-1 (inclusive). For each recursion, it uses constant space (for the call itself) plus T(i) space for the recursive call. But these calls occur one after the other; the space used by each call is releasing before the next call. Therefore they should not be added, but simply the maximum taken. That would be T(n-1), since T is non-decreasing.

Answer 4

The space cmplexity would be O(n). As you have mentioned, it might seem like O(n*n), but one should remember that onces the call for say (i=1) in the loop is done, the space used up in the stack for this is removed. So, you will have to consider the worst case, when i=n-1. Then the maximum number of recursive function calls will be on the stack simultaneously