Fastest Way to Calculate Fibonacci Sequence

Fastest Way to Calculate Fibonacci Sequence

Question

Construct an algorithm so that the Nth item of Fibonacci Sequence can be found in the shortest time. Definition of Fibonacci Sequence is:

 f(n) = 0 , when n = 0 
 f(n) = 1 , when n = 1 
 f(n) = f(n-1) + f(n-2), when n > 1

Solution

There are many solutions for this, the simplest way is to use recursive function.

fibonacci(n) 
    if n equals 0 then return 0 
    else if n equals 1 then return 1 
    else return fibonacci(n-1) + fibonacci(n-2)

There is another way actually, through using loops. The time complexity is O(n).

fibonacci(n) 
    if n equals 0 then return 0 
    else if n equals 1 then return 1 
    fib_n_minus_2 = 0 
    fib_n_minus_1 = 1 
    fib_n = 0 
    for i equals 2 to n 
        fib_n = fib_n_minus_1 + fib_n_minus_2 
        fib_n_minus_2 = fib_n_minus_1 
        fib_n_minus_1 = fib_n 
    return fib_n