Consider the following function:

int $f($int $n)\{$

if $(n==0)$ return $2$;

else if $(n==1)$ return $5$ ;

else$\{$

int val$=2**f(n-1)$;

val$=$val$-f(n-2)$;

return val;

$($a$)$ Write a recurrence relation for the value returned by $f.$ Solve the

recurrence exactly. $($Don$\text{'}$t forget to check it$)$

$($b$)$ Write a recurrence relation for the running time of $f.$ Get a tight

asymptotic bound $($i$.$e$.)$ on the solution to this recurrence.