The Gateway to Computer Science Excellence
+16 votes
2.5k 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 \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!$
in Programming by Veteran (105k points)
edited by | 2.5k views
0
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
All previous GATE questions are answered on site. You can either search them of browse from the "Previous" tab

4 Answers

+36 votes
Best answer

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.

by Veteran (57k points)
edited by
0
How are you getting no of function calls are 2^(n-1)?
0
By checking foo(4). Tree
0
I think the time should be 0(n) for traversing the array to see that the desired value is present in array or not
+5

Without Dynamic Programming Output for foo(5) and Number of function calls are $2^5=32$

Code: https://ideone.com/AoX9zk

With Dynamic programming, the output for foo(5) and Number of function calls are $5+1=6$

Code: https://ideone.com/aaKOen

Time Complexity Reduced to Linear O(n) From exponential $2^n$.

0
@ayush are you saying, in your second code the time complexity is $O(n)$ ?
0
Probably yes.
0
@Debashish-yes.
0
How many states are there ? and time required to update each state ?
0
@Debashish-didn't get you :(. Are you asking for number of distinct function calls?
0

@Debashish Deka-Please let me know where I went wrong.

0
Can we also write double memotable[] instead of double *memo_table(I know this is true, but I am just asking)?
+1

@dd Sir time complexity should be O(n) we are running foo(i) exactly once.

Please help me.

+2
for each function call to foo() , a loop will run. We can total n different foo(x) and each foo takes linear time,
0

@dd
Yeah. Space complexity is $\mathrm{O}(n)$ but the time complexity is $\mathrm{O}(n^2)$.

Because time complexity is calculated against how many times any $\mathrm{O}(1)$ operations happen not actually how many times the function is called. Here '+=' operator is used $\mathrm{O\left(\frac{n(n-1)}{2}\right)}=\mathrm{O}(n^2)$ times using the prescribed optimization.

+16 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)

by Veteran (102k points)
edited by
0
What would be the running time complexity ?
+2

Dulqar  

time complexity is O(n) in this code.

0

@Bikram sir Time complexity for above program is O(N) or O(N2)

0 votes

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)

by Junior (697 points)
0 votes
Could anybody find the time complexity of foo(int n) through recursion tree method.

Thankyou
by (233 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,644 questions
56,505 answers
195,555 comments
101,047 users