Provide tight asymptotic bounds $($i$.$e$.(*)$ on the worst case running times of the following

two procedures. Please provide a very brief explanation of your answer.

$($a$)(7$ points$)$

procedure BackForwardAlg $(n)$

if $n10$ then

return $n$

if $n$ even then

return BackForwardAlg$(\frac{n}{2})$

else

return BackForwardAlg $(n+3)$

$($b$)(7$ points$)$

procedure Recursive Alg$(A[1$dotsn$])$

if $n==1$ then

return False

mid$=|$~$\frac{n}{2}$~$|$

for $i=1$ to mid do

for $j=$mid$+1$ to $n$ do

if $A[i]==A[j]$ then

return True

return $($RecursiveAlg $(A[1$dotsmid$])||RecursiveAlg(A[mid+1$dotsn$])$

$($c$)(2$ points$)$ Give a one sentence description of the meaning of the output of RecursiveAlg.