2
$\begingroup$

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.

$\endgroup$
  • $\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 '16 at 4:34
5
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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