2.4k 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!$

edited | 2.4k 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

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)$

by Veteran (56.8k points)
edited
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$

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

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.

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

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 (101k points)
edited by
0
What would be the running time complexity ?
+2

time complexity is O(n) in this code.

0

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

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 (687 points)

1
2