$1.$ Write a recurrence relation describing the worst case running time of each of the following algorithms and determine the asymptotic complexity of the function defined by the recurrence relation.$$ Justify your solution.$$ You may not use the Master Theorem as justification of your answer.$$ Simplify and express your answer as $($nk$)$ or $($nk log$2$ n$)$ whenever possible.$$ If the algorithm is exponential just give exponential lower bounds.

$$

a$)$ function func$($A$,$n$)$

$$ if n $5$ then return A$(1)$

$$ else

$$ for i $=1$ to n

$$ for j $=$ i to n$-1$

$$ A$($j$)$A$($j$)+$ A$($i$)+3$

$/*$ endfor $*/$

$/*$ endfor $*/$

$$ y $$func$($A$,$ n$-6)$

$$ return $($y$)$

$$

$$

b$)$function func$($A$,$n$)$

$$ if n $2$ then return A$(1)$

$$ y $$func$($A$,$ floor$($n$/3))$

$$ for i $=$ n$-5$ to n

$$ y $$y $+$ A$($i$)+8$

$/*$ endfor $*/$

$$ return $($y$)$

$$

$$