13.

The terms in the Fibonacci sequence are given by :

F₁ = 1, F₂ = 1; F_n = F_n-1 + F_n-2

(a) Give the pseudo-code for a recursive algorithm to calculate the nth term in the Fibonacci sequence.

(b) Give the pseudo-code for a dynamic programming algorithm to compute the nth term in the Fibonacci sequence.

(c) What is the running time of the dynamic programming algorithm.

(d) How does this compare to the running time of the recursive algorithm?