$4.(15$ points$)$ Consider the following recursive algorithm:

$()$

$$: $$

$=11$

$(1)+2$

a$.(2$ points$)$ What does this algorithm compute?

b$.(6$ points$)$ Set up a recurrence relation for the algorithm$$s basic operation count

and solve it $($aka what are $(1)$ and $()).$

c$.(2$ points$)$ What is the efficiency class of this algorithm? Indicate the class

$\backslash$Theta $(())$ the function belongs to$.($Use the simplest $()$ possible in your

answers.$)$

d$.(5$ points$)$ Suggest an improvement, or a better algorithm and indicate its

efficiency class.