Answer to Question 3-2

Question. The fibonacci numbers f0, f1, f2, ... are defined by

   f0 = 0
   f1 = 1
   fn = fn-1 + fn-2  (for n > 1)

The following algorithm is based directly on this definition. 

  f(n)
     if(n < 2) return n
     else return f(n-1) + f(n-2)
Is that an efficient algorithm? If so, explain why. If not, explain why not and describe how to make the algorithm efficient.

Answer. Store the value of f(i) at index i in an array, F. The algorithm is as follows. 

  f(n)
    If n ≤ 1
      return n
    else
      F    = an array with indices from 0 to n.
      F[0] = 0
      F[1] = 1
      for i = 2,...,n
        F[i] = F[i-1] + F[i-2]
      return F[n]
The time is Θ(n). The space is also Θ(n), but that can be reduced by keeping only the two previous values in the sequence.