Complexity of a function: i | CareerCup

Complexity of a function: i | CareerCup

-1     Team: Autopilot     Comment hidden because of low score. Click to expand. 5 Time complexity of Fibonacci function evaluation is Fibonacci function itself. - Flux November 05, 2013 0 of 0 votes Programming functions growth is the mathematical functions? Can u prove it? - urik on bb November 06, 2013 0 of 0 votes As ghost89413 noticed above below, there is recurrent formula for running time T(n) = T(n-1) + T(n-2) For n < 2, T(n) = 1 Which is Fib(n). Another intuitive approach is to notice that we haven't any type of memoisation or result caching for functions call, so final result is sum of 1-s (if "flatten" recursion tree). Fib(n) consists of Fib(n) ones, so complexity is Fib(n). - Flux November 06, 2013 2 of 6 votes the complexity of a naive recursive fibonacci is indeed 2^n. T(n<=1) = O(1) // Understood T(n) = T(n-1) + T(n-2) + O(1) Assume T(n-1) = O(2n-1),

Read full article from Complexity of a function: i | CareerCup