GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
405 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 (77.3k points)   | 405 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

2 Answers

+8 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 (66.3k points)  
selected by
What would be the running time complexity ?
+1 vote

Given program :

#include <stdio.h>
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;
	}
}

int main() {
	double a = foo(5);
	printf("%.2f\n",a);
}

 

And here is the present situation :

Here we can see that, we have lots of overlapping subproblems. Too many function calls.

  1. No of function calls = $2^n$
  2. stack depth used = $O(n)$

Therefore space is linear and time is exponential.

If we take a small number say $4$, then we would have $8.0$ as answer, or we can see that $foo(n) = 2^{n-1}$

and 

  1. stack depth used = $5$.
  2. No of function calls = $2^4 = 16$.

Now using one-dimensional ($1D$) table we can reduce the no of function calls and depth of stack space used as well.

Here is what we want to achieve:

We are reusing already computed $foo(x)$ values. For this purpose, we will be using one $1D$ array of doubles of size $n$.

Here is what we are going to do:

  1. First, check in the $1D$ table for the required call value.
  2. If correct value found: do not call recursive functions
  3. If not, then only attempt for loop recursive calls

Here is the code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define UNUSED 0.5
double *memo_table;
double foo(int n) {
	int i;
	double sum;
	if(memo_table[n] != UNUSED) {
		return memo_table[n];
	}else {
		sum = 0.0;
		for(i=0;i<n;i++) {
			sum += foo(i);
		}
		return memo_table[n] = sum;
	}
}
int main() {
	int n,i;
	scanf("%d",&n);
	memo_table = malloc((1+n)*sizeof(double));
	for(i=0;i<=n;i++) memo_table[i] = UNUSED;
	// base case
	memo_table[0] = 1.0;
	double a = foo(n);
	printf("%lf\n",a);
	free(memo_table);
}

 

Improvements over given program:

  1. Stack space because of function calls reduced to two level only.
  2. Extra space used for the $1D$ array = $O(n)$
  3. More importantly, Time is reduced to $O(n^2)$. (Exponential to Quadratic !! )

 

Overall space complexity = stack + extra = $O(1) + O(n) = O(n) $

Answer B

 

answered by Veteran (47.1k points)  
edited by


Top Users May 2017
  1. akash.dinkar12

    3578 Points

  2. pawan kumarln

    2314 Points

  3. Bikram

    1950 Points

  4. Arjun

    1848 Points

  5. sh!va

    1682 Points

  6. Debashish Deka

    1296 Points

  7. Devshree Dubey

    1282 Points

  8. Arunav Khare

    1122 Points

  9. Angkit

    1072 Points

  10. LeenSharma

    1028 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 29 - Jun 04
  1. Arunav Khare

    246 Points

  2. Arjun

    198 Points

  3. pawan kumarln

    108 Points

  4. Niharika 1

    90 Points

  5. pC

    90 Points


22,909 questions
29,242 answers
65,402 comments
27,744 users