How do I convert the following relation into a recurrence relation?

Question

I am trying to analyse the time complexity of the fast exponentiation method, which is given as

$$x^n= \begin{cases} x^\frac{n}{2}.x^\frac{n}{2} &\text{if n is even}\newline x.x^{n-1} &\text{if n is odd} \newline 1 &\text{if n=0} \end{cases} $$

I tried to write it as, $$ T(n)=\begin{cases} T(\frac{n}{2}).T(\frac{n}{2}) &\text{if n is even}\newline T(n-1) &\text{if n is odd}\newline 1 &\text{if n=0} \end{cases} $$

I think I am lacking somewhere and so not able write correct recurrence relation here.

Need help to do so.

Answer 1

You want to count the total number of multiplications.

So the first case for even $n$ would have:

$$T(n) = 1 + T\left(\frac{n}{2}\right)$$

because you can share the computation of $x^\frac{n}{2}$, performing one additional multiplication to combine them.