Time Complexity of Fibonacci Algorithm
Solution 1
Your recursive code has exponential runtime. But I don't think the base is 2, but probably the golden ratio (about 1.62). But of course O(1.62^n) is automatically O(2^n) too.
The runtime can be calculated recursively:
t(1)=1
t(2)=1
t(n)=t(n-1)+t(n-2)+1
This is very similar to the recursive definition of the fibonacci numbers themselves. The +1
in the recursive equation is probably irrelevant for large n. S I believe that it grows approximately as fast as the fibo numbers, and those grow exponentially with the golden ratio as base.
You can speed it up using memoization, i.e. caching already calculated results. Then it has O(n) runtime just like the iterative version.
Your iterative code has a runtime of O(n)
You have a simple loop with O(n) steps and constant time for each iteration.
Solution 2
You can use this
to calculate Fn in O(log n)
Solution 3
Each function call does exactly one addition, or returns 1. The base cases only return the value one, so the total number of additions is fib(n)-1. The total number of function calls is therefore 2*fib(n)-1, so the time complexity is Θ(fib(N)) = Θ(phi^N), which is bounded by O(2^N).
Koeneuze
Updated on June 28, 2022Comments
-
Koeneuze almost 2 years
So, i've got a recursive method in Java for getting the 'n'th fibonacci number - The only question i have, is: what's the time complexity? I think it's O(2^n), but i may be mistaken? (I know that iterative is way better, but it's an exercise)
public int fibonacciRecursive(int n) { if(n == 1 || n == 2) return 1; else return fibonacciRecursive(n-2) + fibonacciRecursive(n-1); }
-
Konrad Rudolph over 13 years“Iterative is way better” is wrong in general. It’s true that it beats your naive recursive implementation but that implementation can be improved to be essentially on par with an iterative implementation using dynamic programming.
-
-
Koeneuze over 13 yearsAhhh, sorry, i posted the wrong code. I needed the recursive one! My bad, will edit in a sec.
-
CodesInChaos over 13 years@lars That's why I wrote "But of course O(1.62) is automatically O(2) too". But it's still interesting to know a closer upper bound than 2^n.
-
CodesInChaos over 13 yearsNo it's slightly higher. For example Fibo(2) has 3 calls, but returns 2. But for large n the difference doesn't matter much.
-
Fred Foo over 13 yearsO(𝜙 ^ n) = O(2 ^ n) does not directly follow from O(𝜙) = O(2), since O(n^𝜙) != O(n²). I don't this particularly interesting, as there's an O(lg n) (O(n) in the number of bits) algorithm for this problem.
-
CodesInChaos over 13 years@lars sorry it was a typo. I wanted to write
O(1.62^n)
is automaticallyO(2^n)
but forgot the^n