Solve recurrence relation using three methods:

Write recurrence relation of below pseudocode that calculates $$

$$

$,$ 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