patternMinor
Time complexity of the fast exponentiation method
Viewed 0 times
fastthemethodtimecomplexityexponentiation
Problem
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.
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.
Solution
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}
$$
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}
$$
Context
StackExchange Computer Science Q#60858, answer score: 6
Revisions (0)
No revisions yet.