1 votes 1 votes The solution for the recurrence: T(1)=1 T(n) = T(n-1) + T(n-2) + 1 a. log(n) <= T(n)=n b. n<=T(n)<=n2 c. n2 <= T(n)<= 2n d. 2n <= T(n) <=n! Algorithms algorithms recurrence-relation + – targate2018 asked Nov 9, 2017 edited Nov 10, 2017 by targate2018 targate2018 510 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Surajit commented Nov 11, 2017 reply Follow Share fibonacci recurrence, will be O(2^n) ,multiple times you will be calling same problem again and again. 0 votes 0 votes $ruthi commented Nov 12, 2017 reply Follow Share didn't get u 0 votes 0 votes Surajit commented Nov 17, 2017 reply Follow Share the recurrence is that which generates fibonacci sequences,it is just that it calculates same subproblem many no of times that is why its complexity is exponential(just a thought which came in as I was reading dynamic programming,maybe you know this already....:)) ..you can draw a recursion tree to see why it happens so. 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes n <= T(n)<= 2n I think this is the answer and in fib series 1 is not there because, not combining at all in fib series. Pankaj dwivedi answered Jul 1, 2018 Pankaj dwivedi comment Share Follow See all 0 reply Please log in or register to add a comment.