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