GATE 2005
Consider the following C-function:
c
Suppose we modify the above function foo() and store the values of foo(i), 0 <= i < n, as and when they are computed. With this modification, the time complexity for function foo() is significantly reduced. The space complexity of the modified function would be:
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;
}
}