search
Log In
21 votes
3.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
edited by
3.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

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.

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


edited by
0
What would be the running time complexity ?
3

Dulqar  

time complexity is O(n) in this code.

1

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

1 vote

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)

1 vote
Could anybody find the time complexity of foo(int n) through recursion tree method.

Thankyou
Answer:

Related questions

36 votes
3 answers
1
7.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; } } The space complexity of the above code is? $O(1)$ $O(n)$ $O(n!)$ $n^n$
asked Sep 22, 2014 in Programming Kathleen 7.4k views
16 votes
4 answers
2
4.3k views
Consider the following C-program: void foo (int n, int sum) { int k = 0, j = 0; if (n == 0) return; k = n % 10; j = n/10; sum = sum + k; foo (j, sum); printf ("%d,",k); } int main() { int a = 2048, sum = 0; foo(a, sum); printf("%d\n", sum); } What does the above program print? $\text{8, 4, 0, 2, 14}$ $\text{8, 4, 0, 2, 0}$ $\text{2, 0, 4, 8, 14}$ $\text{2, 0, 4, 8, 0}$
asked Sep 22, 2014 in Algorithms Kathleen 4.3k views
12 votes
3 answers
3
3k views
A common property of logic programming languages and functional languages is: both are procedural languages both are based on $\lambda$-calculus both are declarative both use Horn-clauses
asked Sep 22, 2014 in Programming Kathleen 3k views
10 votes
5 answers
4
2.1k views
Which one of the following are essential features of an object-oriented programming language? Abstraction and encapsulation Strictly-typedness Type-safe property coupled with sub-type rule Polymorphism in the presence of inheritance I and II only I and IV only I, II and IV only I, III and IV only
asked Sep 22, 2014 in Object Oriented Programming Kathleen 2.1k views
...