How to estimate the time of completion of following algorithm for Nth Fibonacci element?
private static double fib(double nth){
if (nth <= 2) return 1;
else return fib(nth - 1) + fib(nth - 2);
}
1 Answer
The exact time complexity of this algorithm is... O(F(n)) where F(N) is nth Fibonacci number. Why? See the explanation below.
Let's prove it by induction. Clearly it holds for the base case (everything is a constant). Why does it hold for F(N)? Let's denote algorithm complexity function as T(N). Then T(N) = T(N-2) + T(N-1), because you make 2 recursive calls - one with the argument decreased by 1, one decreased by 2. And this time complexity is exactly Fibonacci sequence.
So F(N) is the best estimation you can make but you can also say this is O(2^n) or more precisely O(phi^n) where phi = (1 + sqrt(5)) / 2 ~= 1.61. Why? Because nth Fibonacci number is almost equivalent to phi ^ n.
This bound makes your algorithm non-polynomial and very slow for numbers bigger than something around 30. You should consider other good algorithms - there are many logarithmic algorithms known for this problem.
7 Comments
J.Olufsen
How can I find out the time needed to find lets say 300th fib element using my algorithm, given that 10th element is calculated in 1ms?
sasha.sochka
Given the formula above you need about 2 * 10^62 operations. Assuming that your computer can make 10^9 operations per second on one core you will need 10^45 years. The earth and sun will die until that.
Boris the Spider
@RCola you need to use
System.nanoTime() to calculate the running time. System.currentTimeMillis() isn't accurate enough.sasha.sochka
@BoristheSpider, I hope you are joking? He needs to wait 10^45 years.
sasha.sochka
No, it's better saying c * (1.61 ^10) = 9193461. You have to find c * (1.61^30). Which is easy to find because c * (1.61^10) = c * (1.61^10)^3 = c * (9193461) ^ 3
|
O(phi^n)time.O(phi^2). This won't be very accurate. Is this an exercise?