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?
<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
<n = ?> : <
return
value> : <number of times called>
n =
0
:
1
2
4
3
8
16
5
32
6
64
7
128
256
9
512
10
1024
number_of_times_called = pow(2, n-1);
@__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
With each addition to the input (n), the growth rate doubles, and the algorithm iterates across all subsets of the input elements. When an input unit is increased by one, the number of operations executed is doubled. O(2^n).
64.3k questions
77.9k answers
243k comments
79.7k users