Time complexity of the fast exponentiation method

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

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>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 & n = 0 \\ S(n-1) + 1 & n \text{ odd} \\ S(n/2) + 1 & n>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 & n \leq 1 \\ S'(n-1) + 1 & n>1 \text{ odd} \\ S'(n/2) + 1 & n>0 \text{ even} \end{cases} $$

Answer 2

You somehow confuse the result of the multiplications and the time they take.

$$x^{n/2}\cdot x^{n/2}$$

does not take $T(\frac n2)\cdot T(\frac n2)$ units of time but $T(\frac n2)+M+T(\frac n2)$ where $M$ denotes the time for a multiplication (assuming they can be done in constant time).

Hence the complete recurrence

$$T(n)=\begin{cases}2T(\frac n2)+M\\T(n-1)+M\\T(1)\end{cases}.$$

We can solve it for the best and worst cases.

Best:

$\frac n2$ decreases $n$ faster than $n-1$. So the best case is achieved when $n$ is a power of $2$, let $2^m$. After $m$ applications of the first line, we have

$$T(2^m)=2^mT(1)+(2^{m-1}+2^{m-2}+\cdots 1)M=2^mT(1)+(2^m-1)M.$$

Worst:

Occurs when every division leads to an odd number, which is when $n$ is a power of $2$ minus $1$. We easily see that every reduction by one bit takes $2M$ multiplications instead of $1$, leading to a similar formula.