PA of Algorithms Q47

47Consider 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 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

Option : B
Explanation :
Space complexity is O (n). The space we need array of size O (n). The space required for recursive call would be O (1) as the value would be taken from array again & again

Forgot your password?

I agree with the Terms.