Time complexity of the fast exponentiation method
Instead of time complexity, it is much simpler here to count multiplications; I'll leave you to figure out the relation between multiplications and time complexity (the exact relation depends on the computation model).

Denote the number of multiplications when computing $x^n$ using your algorithm by $S(n)$.
Let's consider your cases from bottom to top:


Calculating $x^n$ for $n = 0$. The answer is $1$, so no multiplications are needed: $S(1) = 0$.
Calculating $x^n$ for $n$ odd. In this case we first calculate $x^{n-1}$ using the same method, which takes $S(n-1)$ multiplications by definition. Then we multiply the result by $x$, which uses up one multiplication. This gives $S(n) = S(n-1) + 1$ in this case.
Calculating $x^n$ for $n&gt;0$ even. In this case we first calculate $x^{n/2}$ using the same method, which takes $S(n/2)$ multiplications by definition. Then we multiply the result by itself, which uses up one multiplication. This gives $S(n) = S(n/2) + 1$ in this case.


In total, we get the following recurrence for the number of multiplications:
$$
S(n) = \begin{cases}
0 &amp; n = 0 \\
S(n-1) + 1 &amp; n \text{ odd} \\
S(n/2) + 1 &amp; n&gt;0 \text{ even}
\end{cases}
$$
We can improve on the algorithm slightly using the identity $x^1 = x$. This gives the following alternate recurrence:
$$
S'(n) = \begin{cases}
0 &amp; n \leq 1 \\
S'(n-1) + 1 &amp; n&gt;1 \text{ odd} \\
S'(n/2) + 1 &amp; n&gt;0 \text{ even}
\end{cases}
$$