# Time complexity of the fast exponentiation method

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.

• 1. Try editing your question to write down your justification for this equation. Why do you think each case is correct? Where did you get that from? I suspect a bit of "rubber duck debugging" might help you spot a problem in your proposed solution. 2. Then, take a look at cs.stackexchange.com/q/23593/755. This topic also tends to be covered in any decent algorithms textbook. I suggest you study that material, then see if you can get any further, and edit your question with where you're stuck.
– D.W.
Jul 22, 2016 at 4:34

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}$$

• Ok ! when we have a two case relation like $$T(n) = \begin{cases} 0 & n = 0 \\ T(n-1) + 1 & \text{ otherwise} \end{cases}$$ then it become easier to compute Big-O by expanding .How do I compute big-O by expansion for the relation you told me..... Jul 22, 2016 at 11:57
• You'll have to be creative. Jul 22, 2016 at 12:00

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.