GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
356 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 time complexity of the above code is?

asked in Algorithms by Veteran (290k points)  
recategorized by | 356 views
<n = ?> : <return value> : <number of times called>
n = 0 : 1 : 1
n = 1 : 1 : 2
n = 2 : 2 : 4
n = 3 : 4 : 8
n = 4 : 8 : 16
n = 5 : 16 : 32
n = 6 : 32 : 64
n = 7 : 64 : 128
n = 8 : 128 : 256
n = 9 : 256 : 512
n = 10 : 512 : 1024

number_of_times_called = pow(2, n-1);

thanks :)

1 Answer

+10 votes
Best answer

Answer is $O(2^n)$

T(n) = \sum_{i=0}^{n-1} T(i) + cn 

The last $cn$ is for the $n$ times the for loop is executing. 

T(0) = 1
T(1) = 2
T(2) =  5
T(3) = 11
T(4) = 23
T(5) = 47

So,  $$T(n) = 2^n + 2^{n-1} - 1 = O(2^n)$$

answered by Veteran (290k points)  
selected by
explain the recurrence relation???
The sigma term is adding the complexities of all the recursive calls and the "cn" is for the $n$ no. of iterations which also adds to the complexity. If we just do fun(n-1) inside fun(n), recurrence relation will be $$T(n) = T(n-1) + c$$

Here, because of $n$ number of times, a recursive call happens (at the level of n), we have to add $cn$ to the complexity.
Still not clear... can u plz elaborate Sir

 

 

 

I think it will help u

thanks :)

@__PyuriNot clear for me .
When n=2

For ( i=0 ;i < n ; i++)
sum=sum+f(i)

so f(0) is called which returns 1
f(1) will call f(0).

Total of 3  function call and producing a sum of 2

Am i correct ?

In your diagram you showed that their are 5 function calls . How is that possible ?

@arjun Sir , i understood your recurrence .T(n)=Sigma T(i) + cn But didn't follow the solution .

Could you pls explain me how to solve it using

  • Back Substitution


Top Users Aug 2017
  1. ABKUNDAN

    4670 Points

  2. Bikram

    4556 Points

  3. akash.dinkar12

    3420 Points

  4. rahul sharma 5

    3124 Points

  5. manu00x

    2864 Points

  6. makhdoom ghaya

    2450 Points

  7. just_bhavana

    2136 Points

  8. Tesla!

    2042 Points

  9. stblue

    1930 Points

  10. joshi_nitish

    1686 Points


24,970 questions
32,072 answers
74,567 comments
30,150 users