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

Leave a Reply

%d bloggers like this: