GATE CSE 2005 | Question: 81b

Question

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 stores the value of $foo(i) \ 0 \leq 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^2)$
• D. $n!$

Comments

here time complexity is reduced bcz in it we have all value of foo(i) for 0 <=i <n  but to store these value obviously we need extra space i.e we required an array of size n  which holds the value of foo(i)  for i=0 to n so this will take addditionaly o(n) space . or more oer if u reduce the time by some modification that means space will take place

---

All previous GATE questions are answered on site. You can either search them of browse from the "Previous" tab

Answer 1

Requires N units for a plus extra space for n, i and sum, so it's O(N).

Because in this question the value of function foo (i)  vary between 0 to n so its takes total space n so 

Sum = sum + foo(i) 

         = O(1) + O (N)

         = O(N)

so overall space complexity will be O(N)