Question $4[15$ marks$]$

a$)$ Consider the following recursive algorithm.

ALGORITHM A$($n$)$

$//$Input: A positive integer n

if n $=1$ return $1$

else return A$($n $1)+2$ n $$ n $1($i$)$

i$.$ Use the algorithm above to evaluate Q$(4).$

ii$.$ Set up a recurrence relation for this function$$s values $($output$).$

iii.$$ Solve the recurrence relation in $($ii$)$ above to determine what this algorithm computes.

iv$.$ Set up a recurrence relation for the number of multiplications made by this algorithm and solve it$.$

v$.$ Set up a recurrence relation for the number of additions$/$subtractions made by this algorithm and solve it$.$