21 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:

- $O(1)$
- $O(n)$
- $O(n^2)$
- $n!$

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

42 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.

- No of function calls = $2^n$
- 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

- stack depth used = $5$.
- 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:

- First, check in the $1D$ table for the required call value.
- If correct value found: do not call recursive functions
- 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:

- Stack space because of function calls reduced to two level only.
- Extra space used for the $1D$ array = $O(n)$
- 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.**

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

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

2

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

1

@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)**