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.