Gate CS-2005 Question Paper With Solutions

Q. 82 Consider the following C-function:

double foo(int n)
{
    int i;
    double sum;
    if(n == )
    {
        return 1.0;
    }
    else
    {
        sum = 0.0;
        for(i = ; i < n; i++)
        {
            sum += foo(i);
        }
        return sum;
    }

}

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:

(A) O(1)

(B) O(n)

(C) O(n!)

(D) O(nⁿ)

Answer: (B)

Explanation: