Design an algorithm which computes $3^n$ using only clogn instructions for some

positive constant c$.$ Hint: Write a method based on the following recursive

formulation of $3^n$ carefully.

$3^n=\{\begin{array}{ccc}1& if& n=0\\ 3^{\frac{n}{2}}**3^{\frac{n}{2}}& if& n\%2==0\\ 3^{\frac{n}{2}}**3^{\frac{n}{2}}**3& if& n\%2==1\end{array}$