Calculation of the spatial 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 complexity of the space of the above function:

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

What I have done is calculating the repetition ratio for the above code, but I still cannot solve this repetition. I know this is not a work-related home site. But any help would be appreciated.

This is my repetition.

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

Where S is some constant.

Answer 1

It will depend on whether you are talking about the stack or complexity with a bunch.

For the heap, this is O(1) or O(0) , since you are not using heap memory. (except for main utility utilities / programs)

For the stack, this is O(n) . This is because recursion raises N levels in depth.

The deepest point:

 foo(n) foo(n - 1) foo(n - 2) ... foo(0) 

Answer 2

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

Edit: ... so much to make you understand the solution for yourself :)

Answer 3

You do not explain how you derived your repetition attitude. I would do it like this:

• If n == 0, then foo uses constant space (no recursion).
• If n> 1, then foo repeated once for each i from 0 to n-1 (inclusive). For each recursion, it uses a constant space (for the call itself) plus T (i) space for the recursive call. But these challenges occur one after another; the space used by each call is freed until the next call. Therefore, they should not be added, but simply take the maximum. This will be T (n-1), since T is non-decreasing.

Answer 4

The bulkiness of the space would be O (n). As you already mentioned, this may seem O (n * n), but remember that after the call to say (i = 1) in the loop is completed, the space used on the stack for this will be deleted. So you will need to consider the worst case where i = n-1. Then the maximum number of calls to recursive functions will be on the stack at the same time