+5 votes
594 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
recategorized | 594 views
+2
<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);

0
thanks :)

## 1 Answer

+10 votes
Best answer

Answer is $O(2^n)$

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 (400k points)
selected by
+1
explain the recurrence relation???
+1
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.
0
Still not clear... can u plz elaborate Sir
0 I think it will help u

0
thanks :)
0

@Not 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 ?

0

@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

+5 votes
2 answers
3
0 votes
2 answers
7