Consider the following function $fn.$

int $fn(n)\{$

if $(n==0$

return $1$ ;

$\}$

if

return $2$;

$\}$

return $2**fn(n-2)+fn(n-1)$;

$\}$

$($a$)$ Compute the value $fn(5).$ Show the steps in your computation. $[6$

marks$]$

$($b$)$ Illustrate all recursive calls made by the algorithm on input $n=5,$

i$.$e$.,$ when calling $fn(5),$ by drawing the recursion tree. $[6$ marks$]$

$($c$)$ What does $fn(n)$ compute for $n0?$ Justify your answer. $[6$ marks$]$

$($d$)$ Compute an estimate of the execution time as a function of $n.$ Give

your answer in Big$-$Oh notation and justify your answer. $[6$ marks$]$ part a is solved please solve the rest