# 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 '16 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..... – Aditya pratap singh Jul 22 '16 at 11:57
• You'll have to be creative. – Yuval Filmus Jul 22 '16 at 12:00