Why is the complexity of computing the Fibonacci series 2^n and not n^2?

by

The complexity of a naive recursive fibonacci is indeed 2ⁿ.

T(n) = T(n-1) + T(n-2) = T(n-2) + T(n-3) + T(n-3) + T(n-4) = 
= T(n-3) + T(n-4) + T(n-4) + T(n-5) + T(n-4) + T(n-5) + T(n-5) + T(n-6) = ...

In each step you call T twice, thus will provide eventual asymptotic barrier of:
T(n) = 2⋅2⋅...⋅2 = 2ⁿ

bonus: The best theoretical implementation to fibonacci is actually a close formula, using the golden ratio: 

Fib(n) = (φⁿ – (–φ)⁻ⁿ)/sqrt(5) [where φ is the golden ratio]

(However, it suffers from precision errors in real life due to floating point arithmetics, which are not exact)

More Related Contents:

  1. Is log(n!) = Θ(n·log(n))?
  2. Why is my recursive function so slow in R?
  3. complexity in terms of big O
  4. time complexity of recursion function
  5. Big O, how do you calculate/approximate it?
  6. What is tail call optimization?
  7. Can hash tables really be O(1)?
  8. Why is the constant always dropped from big O analysis?
  9. How can building a heap be O(n) time complexity?
  10. Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations
  11. Big-O for Eight Year Olds? [duplicate]
  12. How to find all combinations of coins when given some dollar value [closed]
  13. Which algorithm is faster O(N) or O(2N)?
  14. recursion versus iteration
  15. Design patterns for converting recursive algorithms to iterative ones
  16. Finding out nth fibonacci number for very large ‘n’
  17. Computing set intersection in linear time?
  18. Basic Recursion, Check Balanced Parenthesis
  19. Test if a number is fibonacci
  20. Examples of Algorithms which has O(1), O(n log n) and O(log n) complexities
  21. Quicksort superiority over Heap Sort
  22. Big O when adding together different routines
  23. Time Complexity of two for loops [duplicate]
  24. Finding height in Binary Search Tree
  25. An inverse Fibonacci algorithm?
  26. Difference between Big-Theta and Big O notation in simple language
  27. Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin
  28. Can a Fibonacci function be written to execute in O(1) time?
  29. Why is bubble sort O(n^2)?
  30. Convert recursion to tail recursion

Leave a Comment