GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
303 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 (280k points)  
recategorized by | 303 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

+8 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 (280k 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 Feb 2017
  1. Arjun

    5278 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3942 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2378 Points

  6. sriv_shubham

    2308 Points

  7. Smriti012

    2236 Points

  8. Arnabi

    2008 Points

  9. sh!va

    1672 Points

  10. mcjoshi

    1648 Points

Monthly Topper: Rs. 500 gift card

20,846 questions
26,002 answers
59,657 comments
22,100 users