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.

  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jul 22, 2016 at 4:34

2 Answers 2


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

  • $\begingroup$ 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..... $\endgroup$ Jul 22, 2016 at 11:57
  • 2
    $\begingroup$ You'll have to be creative. $\endgroup$ 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.


$\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.$$


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.