$1\mathrm{.}6$ Problem $6[60$ pts$]$

Problem $6.$ The sequence F$\_($n$)$ of Fibonacci numbers is defined by the recurrence relation

F$\_($n$)=$F$\_($n$-1)+$F$\_($n$-2)$

with seed values F$\_(0)=1$ and F$\_(1)=1.$

$(10$ pts$)$ Consider the recursive top$-$down implementation of the recurrence $(1)$ for calculating n$-$th Fibonacci

number F$\_($n$).$

$($a$)$ Write down an algorithm for the recursive top$-$down implementation in pseudocode.

$($b$)$ Write down the recurrence for the running time T$($n$)$ of the algorithm and solve for it$.$

Answer.