$(3$ points$)$ Given the following recurrence relation:

T$($n$)=4$T$($ n

$16)+$ n$2+$ n $+1$

$($a$)(2$ points$)$ Compute the complexity of the recurrence using the Back$-$Subtitution method

as learned during our lectures. Show all your work step$-$by$-$step, including at least $3$

substitutions before you move to k steps. Also, solve any summations computed during

the process. Your final result must be a function of n$.$ Work provided using approaches

that were not covered in class WILL NOT get credit. No exceptions!

$($b$)(1$ point$)$ Check your result from $($a$)$ using the Master Theorem. In your Master Theorem

approach you must clearly state the values of f$($n$),$ a$,$ b$,$ k$,$ p$,$ logb a and show clearly

step$-$by$-$step all your work.