Consider the following C-function: C double foo (int n){ int i; double sum; if…
2005
Consider the following C-function:
C
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(nn)
Attempted by 82 students.
Show answer & explanation
Correct answer: B
Answer: O(n). The space complexity is O(n) because the maximum recursion depth grows linearly with n.
Each active function call uses O(1) additional space for local variables and return information.
Inside foo(n) the loop calls foo(i) for smaller i, and the longest chain of nested calls is foo(n) → foo(n-1) → ... → foo(0), giving O(n) active stack frames in the worst case.
Although the total number of calls (time complexity) may be much larger, calls are executed sequentially, so only the maximum call depth contributes to concurrent memory usage.
Therefore the space complexity is O(n).