algorithmcomplexity-theoryfibonacci

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

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?

Solution

  • 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...