GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
298 views
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 <= 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:

  1. $O(1)$
  2. $O(n)$
  3. $O(n^2)$
  4. $n!$
asked in Algorithms by Veteran (75.6k points)   | 298 views
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

1 Answer

+6 votes
Best answer

The modification being proposed is tabulation method of Dynamic Programming.

So let we have an auxillary array which stores the value of foo(i) once it is computed and can be used at later stage .So foo(i) is not called again , instead lookup from the table takes place. It would be something like :

#include <stdio.h>
#define max 1000
int foo[max];
foo(int n) {
	if(foo[n] == -1) //compute it and store at foo[n] and return
	else // return foo[n] directly
}
int main(void) {
	//initialize all elements of foo[max] to -1  
	return 0;
}

Using this approach , we need an auxillary array of size $n$ to store foo(i) where $i$ ranges from $0$ to $ n-1$.

So space complexity of this method =   $O(n)$ And function foo(n) computes $2^{n-1}$

Hence the correct option should be B)

answered by Veteran (65k points)  
selected by
What would be the running time complexity ?
Top Users Feb 2017
  1. Arjun

    5278 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3942 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2378 Points

  6. sriv_shubham

    2308 Points

  7. Smriti012

    2236 Points

  8. Arnabi

    2008 Points

  9. sh!va

    1672 Points

  10. mcjoshi

    1660 Points

Monthly Topper: Rs. 500 gift card

20,857 questions
26,009 answers
59,671 comments
22,107 users