# Recurrence relation for this exponentiation algorithm

I am trying to come up with a recurrence relation for the number of multiplications needed for this algorithm:

EXP(x,e):
if e = 0, return 1
else
r = EXP(x, floor(e/2))
if e is even
return r*r
else
return r*r*x


I have calculated the number of multiplications needed for some values of e:

e = 0, 0 multiplications
e = 1, 2 multiplications
e = 2, 5 multiplications
e = 3, 6 multiplications
e = 4, 7 multiplications
e = 5, 12 multiplications
e = 6, 13 multiplications
e = 7, 14 multiplications

I am unable to find a pattern for them. I was trying, for example, to find a recurrence relation starting as $T(n) = 2*T(\frac{n}{2}) + (abc)$ but am unable to find a common (abc).

One thing I have noticed, but don't think leads anywhere, is that if you look at e=2,3,4 you have T(n) = T(n-1) + 1 for those, same thing for e=5,6,7. But obviously that doesn't work for the jump between e=4 and e=5.

Could anyone provide some help/hints?

Thank you.

• Your counts seem to be wrong -- the only difference between $e=4$ and $e=5$ is a single multiplication by $x$, so the difference between those two counts should be $1$. Commented Oct 16, 2015 at 20:13

## 1 Answer

A problem of size $$e$$ can have the subproblem size $$e'$$ either as $$e/2$$ or $$(e-1)/2$$, depending upon the parity of $$e$$. Also, at the problem level itself, there can be either 1 or 2 multiplications, again depending upon the parity of $$e$$. I think finding the multiplication count via recurrence-relations may not be simple. But we can try counting them in another way as below.

Consider the binary representation of $$e$$; say it has $$m$$ bits. Then, the subproblem size $$e'$$ is actually the bits of $$e$$ right-shifted by 1 place (for both even and odd $$e$$). So, $$e'$$ must have $$m-1$$ bits. At the problem level itself, number of multiplications is 1 if the least-significant-bit (LSB) of current $$e$$ is 0 (even $$e$$), else it is 2.

In this new perspective of the algorithm, we can count the multiplications as follows. Total subproblem instances are $$m$$. Each subproblem does 1 or 2 multiplications based on the bit (LSB). So, if initial $$e$$ has $$p$$ 1 bits, and $$(m-p)$$ 0 bits, total multiplications are:

$$2 \cdot p + 1 \cdot (m-p) = p + m$$