Menu
I am trying to find complexity of Fibonacci series using a recursion tree and concluded height of tree = O(n) worst case, cost of each level = cn, hence complexity = n*n=n^2
How come it is O(2^n)?
472
The time complexity of the Fibonacci series is T(N) i.e., linear. We have to find the sum of two terms, and it is repeated n times depending on the value of n. The space complexity of the Fibonacci series using dynamic programming is O(1).
The time complexity of the Fibonacci Search Algorithm is O(logn) . The best-case time complexity is O(1) . It occurs when the element to be searched is the first element we compare.
I recently solved the time complexity for the Fibonacci algorithm using recursion. This is a standard solution with a time complexity of O(2^n).
Time Complexity: Hence the time taken by recursive Fibonacci is O(2^n) or exponential.
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)
173
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
