Consider the following C-function: double foo (int n) { int i; double sum; if…

GATE · 2005 · CS

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;
    }
}

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!)

Attempted by 319 students.

Explore the full course: Gate Guidance By Sanchit Sir