How to calculate the time of recursive computation of n-th Fibonacci number?

Question

What is the way to know how much time is needed for computation n-th Fibonacci number on current machine? For instance, on current machine the 30-th element is calculated in 67ms, and 40th in 554 ms. How to calculate the time for 99th element?

int fib(int n)
{
    if( n <= 2) 
        return 1
    else
        return fib(n-1) + fib(n-2)
}

UPDATE

Fibonacci Nth vs ms (the time current pc took to calculate n-th fibonacci element, time in ms) http://pastebin.com/PGnd54Hq

Matlab: Code http://pastebin.com/L9CH53Pf

Graph

How to find out the time for N-th element?

What do you mean by "current machine"? The question is kind of unclear. Also, any kind of estimation will depend on what kind of algorithm it is. Is it tail recursive? Is it pushing a stack frame every call? What are you getting at with this question? — Tyler Durden, Oct 11 '12 at 20:08
My machine- current PC the recursive algorithm is running on. Probably another possible solution is to find out how many steps needed (totally) and multiply this by the time of one step. But how can I calculate the time necessary for one step? — J.Olufsen, Oct 11 '12 at 20:42

score 2 · Accepted Answer · edited May 23 '17 at 12:07

I would measure the time for a range of values and make table:

n | time

and then use matlab to fit to an exponential function.

keep in you mind that big-O notation is asymptotic and holds for a big number of elements.

enter image description here

you should try to write a c code for it. using inline function of the Fibonacci routine, and get the time in using ctime and store the values in two arraies. and after that analyzing the results using matlab or `python.

please post your outcomes...

score 2 · Answer 2 · answered Oct 11 '12 at 16:27

It's easy to prove that the number of recursive calls to the function also follows a Fibonacci sequence. Like, if F0=0 and F1=1 are your base cases then F2 requires 2 calls to the function and F3 will need 3 and so on.

This justifies using an exponential function to fit your times as @0x90 suggested.

score 2 · Answer 3 · edited May 23 '17 at 11:53

2

Apparently you are running an implementation of naive algorithm for computing Fibonacci sequence. This algorithm has an exponential complexity: Computational complexity of Fibonacci Sequence (~θ(1.6ⁿ)). So running time of your program on your computer will be approximately k*1.6ⁿ. Knowing the result of the function (your program's running time) for one n you should be able to calculate the constant k and thus calculate approximate time for different n.

edited May 23 '17 at 11:53

Community

1
1

answered Oct 11 '12 at 16:29

piokuc

25,594
11
72
102

Cannot understand why this formula does not show real time algorithm needed. In question's example, th time to compute 40th element is 554ms and 30th -67ms. Using this formula k= (67/(1.6^30)) and T[40]=( (67/(1.6^30)) *1.6^(40)) but it is not correct. http://www.wolframalpha.com/input/?i=%28%2867%2F%281.6%5E30%29%29*1.6%5E%2840%29%29 – J.Olufsen Oct 11 '12 at 21:08

Bert te Velde · Answer 4 · 2012-10-22T09:35:25.363

Performance is not only determined by the number of function calls and the number of calculations inside each call, but also by what you pay - time-wise - for pushing ever more on the stack due to the recursive algorithm. I do not know how that stack-pushing performs but it is likely that it starts to increase more rapidly after a certain threshold. So, you'll have to find out where this threshold kicks in and fit (exponentially or whatever) both below and above (and maybe there are more similar performance penalties when you start to build up the recursive-stack).

Obviously - although that's not in the question - fibonacci numbers shouldn't be computed in a recursive way, even though that's mathematically elegant and requires the most simple code.

[ADDED/EDITED] I noticed that you have added a graph of time measurements. To get better insight, I suggest to use a LOGARITHMIC scale vertically (times). This will show more clearly whether the whole graph is "purely" exponential - a straight line on a logarithmic plot - or whether it is rather a sequence of (different) exponentials or yet something else. Possibly, the exponential part starts "somewhere", or changes into another exponential.

score 0 · Answer 5 · answered Oct 11 '12 at 20:52

From the code listed each call makes 2 calls. So a simple answer to this question is that the number of calls doubles for each n, so the number of calls is 2^(n-1). For example, if you are calculating fib( 10 ), then the number of calls would be 2^9 = 512. So, if it took 1 second to make one, it would take 512 seconds to make all the calls for fib( 10 ).

How to calculate the time of recursive computation of n-th Fibonacci number?

5 Answers5