Consider the following functions:

int recursive$($int n$)$

$\{$

if $($n $<=1)\}$

$\}$

return $1$; else

return recursive$($n $-1)+$ recursive$($n $-1)+$ recursive$($n $-1)$;

a$)[5$pts$]$ What does this function calculate?

b$)[5$pts$]$ Give a recurrence relation $($T$($n$)=...)$ for this function. Include both base and recursive cases$)$

c$)[10$pts$]$ Solve the recurrence relation to get the $\backslash$Theta $(...)$ running time of the function, in terms of n$.$ Show

your work, using the substitution method and the recursion tree.$)$ running time of the function $,$ in terms of n$.$ Show your work, using the subtitutaion method and recoursion tree.