Interview Practice 19 - 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:

= 0 , when n = 0 f(n) = 1 , when n = 1 = 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

Show Comments