edited by
10,770 views
35 votes
35 votes
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:

  1. $O(1)$
  2. $O(n)$
  3. $O(n^2)$
  4. $n!$
edited by

5 Answers

Best answer
60 votes
60 votes

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 is B.

edited by
18 votes
18 votes

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)

edited by
2 votes
2 votes
Could anybody find the time complexity of foo(int n) through recursion tree method.

Thankyou
2 votes
2 votes

For part one of the question (NON-DP)

Space Complexity: T(n-1) + 1

Time Complexity: 2T(n-1) + 1

Reason: One T(n-1) for i=0 to n-2 and other T(n-1) for i=n-1.

For this 2nd part of the question (DP)

Space Complexity: No recurrence relation required.

Time Complexity:T(n-1)+n

Reason: only one T(n-1) for i=0 to n-1 and doing work n times.

Answer:

Related questions

53 votes
53 votes
5 answers
1
Kathleen asked Sep 22, 2014
18,926 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; } }The space complexity of the a...
13 votes
13 votes
3 answers
3
Kathleen asked Sep 22, 2014
12,351 views
A common property of logic programming languages and functional languages is:both are procedural languages both are based on $\lambda$-calculusboth are declarativeboth us...