procedure f$($x$,$n$)\%$ x is a real number, n is a natural number

if n$==0$

return $1$ else

if n is even

a $=$ f$($x$,$n$/2)$

return a$*$a

else

a $=$ f$($x$,($n$-1)/2)$

return x$*$a$*$a

end if

end if

end procedure

$($a$)$ Briefly describe what this algorithm computes.

$($b$)$ Write a recurrence relation for its computation complexity. Then, find the computational complexity of the given algorithm based on the master theorem: ForT$($n$)=$aT$($n$/$b$)+$cnd withn$=$bk$,$ k in Z$+,$ a$>=1,$ b$>1,$ c$>0,$ d$>=0,$

$$O$($nd$),$

T$($n$)$ is $$O$($nd logn$),$

$$

$$O$($nlogb a$),$

if a $<$ bd$,$ if a $=$ bd$,$ if a $>$ bd$.$

$($c$)$ Write an equivalent iterative algorithm. Then find its complexity and compare it to the given algorithm.