Consider the following pseudocode.

Alg$($n$)$:

If n $3$ then

return $1$

x $=$ Alg$($n $2)$

y $=$ Alg$($n $4)$

return x $+$ y$.$

$($a$)(5$ points$)$ Describe the running time T $($n$)$ of Alg$($n$)$ as a recurrence relation.

$($b$)(15$ points$)$ Use the substitution method to prove that T $($n$)=$ O

$1+5$

$2$

$$ n

$2$

$.($Useful

Fact:

$1+5$

$2$

$2$

$=$

$1+5$

$2$

$+1)$