-
A recursive program to compute Fibonacci numbers is shown below. Assume you are also given an array f[0...m] with all elements initialized to 0.
(a) Fill in the boxes with expressions/statements to make fib() store and reuse computed Fibonacci values. Write the box number and the corresponding contents in your answer book.
(b) What is the time complexity of the resulting program when computing fib(n)?
-
- f(n)3 0 , 0 (n3)
- 1
- 2
- None of these
Correct Option: A
(a) (1) f[n]! = 0
or
Expression like f(n)3 0 etc.
(2) f[n]
(3) f[n] = t
(b) O(n) or (n + 1)
Alternately 0 (n3) in the log-cost model.