0 votes 0 votes How fibonacci timecomplexity on dynamic approach and recursive approach is different Couldnt understand the algo properly If someone could help :) A_i_$_h asked Nov 16, 2017 A_i_$_h 434 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Rupendra Choudhary commented Nov 16, 2017 reply Follow Share Hope you know , in recursive approach as there would be n level tree ans in worst case it may be a complete binary tree means 2n-1 nodes means 2n-1 function calls so TC would be O(2n) You can guess in recursive approach many function calls would have been repeated , and eventually we are computing same calculation many times , which is of course a disadvantage so in here in dynamic programming , we will compute only distinct function calls , a subproblem that is being evaluated , would never ne evaluated again because we will save it in some array ans when we need it next time , from array we just catch it's output. in that way the TC of dynamic programming is evaluated as TCdp= # of distinct function calls * 1 function call cost and there as n+1 distinct function calls for fib(n). for fib(5) we need fib(0), fib(1), fib(2),fib(3),fib(4),fib(5) so 'n+1' distinct function calls..and each function call will correspond to one addition operation like fib(n)=fib(n-1)+fib(n-2) , so one addition cost so eventually complexity = (n+1)*O(1)=O(n) 2 votes 2 votes Surajit commented Nov 17, 2017 reply Follow Share Draw a recursion tree you will understand yourself.Also note what will be the effect if we use same recursive procedure but we keep on storing intermediate results in a table for lookup. 0 votes 0 votes Please log in or register to add a comment.