$3.($a$)$ Given the following algorithm, write down the recurrence equation for the run$-$time of the

problem.

$(2$ pts$)$

int S$($int N$)$

$\{$

if$($N $==0||$ N $==1)$

return $1$;

else

return S$($N$-1)*$ S$($N$-2)$;

$\}$

$($b$)$ Using the same function, evaluate the value of S$(5).$ Show the steps. $(5$ pts$)$

c$)$ What are the three steps of a divide and conquer algorithm? Is the function given in problem $3($a$)$

is based on divide and conquer, explain.