Consider the following algorithm exp$($a$,$n$)$ that computes an$.$ Let Cn be the number of

$($a$,$ n$).$ mulitplication performed by exp

exp$($a$,$n$)\{$

if $($n $==1)$

return$($a$)$;

m$=$ n$/2$; $//$ integer division

$\}$

power$=$ exp$($a$,$m$)$;

power $=$ power $*$ power

if $($n is even$)$

return $($power$)$ ;

else

return$($power $*$a$)$;

$1$

$($a$)(3\%)$ Prove that exp$($a$,$n$)$ is correct. $($That is$,$ show that exp$($a$,$n$)$ returns an$.)$

$($b$)(3\%)$ Give a recurrence equation for Cn$.($Hint: consider $2$ cases: n is even and n is

odd.$)$

Solve the recurrence equation in case n is a power of $2.($c$)(3\%)$

$($d$)(3\%)$ Give an example where Ci $>$ Cj and i $<$ j$.$

$($e$)(3\%)$ Show that Cn $=$ E$>($log$($n$))$