5 votes 5 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; } } The time complexity of the above code is? Algorithms time-complexity space-complexity algorithms normal + – Arjun asked Aug 29, 2014 • recategorized Sep 14, 2014 by gatecse Arjun 2.6k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Prasanna commented Dec 19, 2015 reply Follow Share <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); 2 votes 2 votes Gate Mm commented Dec 19, 2015 reply Follow Share thanks :) 0 votes 0 votes Please log in or register to add a comment.
Best answer 11 votes 11 votes Answer is $O(2^n)$ $T(n) = \displaystyle \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)$$ Arjun answered Aug 29, 2014 • selected Sep 1, 2014 by Arjun Arjun comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments Gate Mm commented Dec 19, 2015 reply Follow Share thanks :) 0 votes 0 votes pC commented Jan 26, 2016 reply Follow Share @__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 ? 0 votes 0 votes pC commented Jan 26, 2016 reply Follow Share @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 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes 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). Rahul_kumar3 answered Oct 18, 2023 Rahul_kumar3 comment Share Follow See all 0 reply Please log in or register to add a comment.