Computational Complexity Of Fibonacci Sequence
Answer : You model the time function to calculate Fib(n) as sum of time to calculate Fib(n-1) plus the time to calculate Fib(n-2) plus the time to add them together ( O(1) ). This is assuming that repeated evaluations of the same Fib(n) take the same time - i.e. no memoization is use. T(n<=1) = O(1) T(n) = T(n-1) + T(n-2) + O(1) You solve this recurrence relation (using generating functions, for instance) and you'll end up with the answer. Alternatively, you can draw the recursion tree, which will have depth n and intuitively figure out that this function is asymptotically O(2 n ) . You can then prove your conjecture by induction. Base: n = 1 is obvious Assume T(n-1) = O(2 n-1 ) , therefore T(n) = T(n-1) + T(n-2) + O(1) which is equal to T(n) = O(2 n-1 ) + O(2 n-2 ) + O(1) = O(2 n ) However, as noted in a comment, this is not the tight bound. An interesting fact about this function is that the T(n) is asymptotically the same as the value of Fib(n) since both are de...