How to estimate the time of Fibonacci recursive algorithm for nth element?

Question

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);
    }

You mean complexity? Or actual time? The algorithm runs in `O(phi^n)` time. — Boris the Spider, Sep 21 '13 at 14:44
I need actual time(how long would it take to calculate Nth element). How to calculate this **O(phi^n)** for example for 200th Fibonacci number? — J.Olufsen, Sep 21 '13 at 14:50
Run it for elements 1..10 then you extrapolate using the fact that it's `O(phi^2)`. This won't be very accurate. Is this an exercise? — Boris the Spider, Sep 21 '13 at 14:56
Yes. I have got 45th in 6452 ms; and 10th in 1ms. How to calculate time for 200th? — J.Olufsen, Sep 21 '13 at 14:57
Why not use the [closed form](http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression)? — Boris the Spider, Sep 21 '13 at 14:58

sasha.sochka · Accepted Answer · 2013-09-21T15:04:38.400

2

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.

edited Sep 21 '13 at 15:04

answered Sep 21 '13 at 14:58

sasha.sochka

14,395
10
44
68

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? – J.Olufsen Sep 21 '13 at 15:06
1

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. – sasha.sochka Sep 21 '13 at 15:09
@RCola you need to use `System.nanoTime()` to calculate the running time. `System.currentTimeMillis()` isn't accurate enough. – Boris the Spider Sep 21 '13 at 15:09
@BoristheSpider, I hope you are joking? He needs to wait 10^45 years. – sasha.sochka Sep 21 '13 at 15:10
I'm just saying that if the OP wants to estimate the running time by extrapolating from the time for one calculation then `nanoTime` needs to be used. – Boris the Spider Sep 21 '13 at 15:11
OK. Using nanoTime() I have got 9193461ns for 10th element. =>n^10=9193461 => find out **n** => put **n** to power 300 for 300th element = time in nanoseconds. Correct? – J.Olufsen Sep 21 '13 at 15:34
1

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 – sasha.sochka Sep 21 '13 at 16:01

How to estimate the time of Fibonacci recursive algorithm for nth element?

1 Answers1