Now consider the following recurrence $()$:

$()=\{$

$1,$ if $<16$

$2($

$16)+$

$,$ if $16$

$8.(3$ points$)$ Use the repeated substitution method to come up with a function $()$ that constitutes a

good guess on the asymptotic complexity of recurrence $().$ Hint: use sentinels to simplify the

analysis.

$9.(3$ points$)$ State and prove by induction a theorem showing $()$ in $(())$ for the same function

$()$ guessed above. Hint: use sentinels to simplify the analysis.

$10.(3$ points$)$ State and prove by induction a theorem showing $()$ in $(())$ for the same function

$()$ guessed above. Hint: use sentinels to simplify the analysis.

$11.(1$ point$)$ Now use the Master Theorem to solve the same recurrence.