edited by
838 views
0 votes
0 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;
    }

}

Q1]  What is the running time complexity of the algorithm ?

Q2] What is the change in running  time complexity when  we modify the  above function foo() and store the values of foo(i) 0<i<n as and when they are computed . Please tell how the code will look like in first place

Please explain in detail how to analyse it

edited by

1 Answer

1 votes
1 votes

here,for every valueof 'i',function call for foo(i) + all the function calls for numbers < i are considered.

lets suppose,we take, n=10

then

in first iteration, i=0 -> here just foo(0) is called.it takes 1 function call and it returns to for loop again.

in next iteration,then i=1 -> here we count foo(1) and then foo(0) (observe for loop carefully) hence,here 2 function calls are there

in next iteration, i=2 -> we call foo(2) -> foo(0) -> foo(1) ,now,1 function caall for foo(0) and  for foo(1) ,there are already 2 function calls(see above).therefore,we require 4 function calls for i=2

in next iteration ,i=3 -> we call foo(3) -> foo(0) -> foo(1) -> foo(2) ,now 2 function calls for foo(1) and 4 function calls for foo(2)

,hence 8 function calls at i=3

solvind like this,we get 1+2+4+8+16+....n

finally we get,2n

so,T(n) for first part should be O(2n)

please verify this

Related questions

8 votes
8 votes
2 answers
1
1 votes
1 votes
2 answers
2
APOORV PANSE asked Jun 1, 2016
2,987 views
Consider the following c fragment : void DAA(n) { int i,j,k,x=0; for (i=1 ; i <=n ; i++) for (j=1 ; j <= i * i ; j++) { if ( j mod i == 0 ) for ( k = 1 ; k <= j ; k++) x=...
0 votes
0 votes
1 answer
3
Rohit Pandey asked Jun 27, 2018
765 views
What will be the time complexity if fractional knapsack is implemented using min heap instead of sorted arraya) O(nlogn)b)O(n^2)c)O(n)d) none of these
3 votes
3 votes
1 answer
4
pC asked Sep 22, 2017
2,506 views
Explain Prims AlgorithmAnalysis Of Time ComplexityHow does $\mathcal{O}(VlogV + ElogV)=\mathcal{O}(ElogV)$