Write recurrence relation of below pseudocode that calculates x$^$n$,$ and solve the

recurrence relation using three methods that we have seen in the explorations.$$power$2($x$,$n$)$:

if n$==0$:

return $1$

if n$==1$:

return x

if $($n$\%2)==0$:

return power$2($x$,$ n$//2)*$ power$2($x$,$n$//2)$ else:

return power$2($x$,$ n$//2)*$ power$2($x$,$n$//2)*$ x