# [Leetcode][50. Pow(x, n)] The Illustration of Fast Power Algorithm - Exponentiation by Squaring or Binary Exponentiation

**By Long Luo**

This article is the solution of Problem 50. Pow(x, n).

1 | 50. Pow(x, n) |

We know how to find `2.0`

raised to the power `10`

. The easiest way is to multiply `10`

times `2.0`

by loop, but what if we have to find `2.0`

raised to the power very large number such as `10000`

or more?

We will discuss how to find the solution of such problems by using an fast, efficient algorithm.

# Brute Force

We multiply $a$ to itself $b$ times. That is, $a^b = a \times a \times a \times ... \times a (b occurrences of a)$.

A simple java implementation of that would be:

1 | public static double myPow(double x, int n) { |

## Analysis

**Time Complexity**: $O(n)$**Space Complexity**: $O(1)$

# Exponentiation by Squaring

Exponentiation by Squaring can help us in finding the powers of large positive integers. The key is to the **divide the power in half** at each step.

The following recursive approach expresses the same idea:

$a^n = \begin{cases} 1 &\text{if } n == 0 \\ \left(a^{\frac{n}{2}}\right)^2 &\text{if } n > 0 \text{ and } n \text{ even}\\ \left(a^{\frac{n - 1}{2}}\right)^2 \cdot a &\text{if } n > 0 \text{ and } n \text{ odd}\\ \end{cases}$

Let’s take an example:

1 | 3 ^ 10 = 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 |

Effectively, power is divided by $2$ and base is multiplied to itself. So we can write $3^10 = 9^5$.

Now, our problem is to find $9^5$.

1 | 9 ^ 5 = 9 * 9 * 9 * 9 * 9 |

Effectively, when power is not divisible by $2$, we make power even by taking out the extra $9$. Then we already know the solution when power is divisible by $2$. Divide the power by $2$ and multiply the base to itself.

Now our problem is to find $(81^2)*9$

1 | (81 ^ 2) * 9 = (81 * 81) * 9 |

Finally, we have our solution $3^10 = (6561^1)*9 = 6561*9 = 59049$

Let’s use **recusive** in java.

1 | public static double myPow_quick(double x, int n) { |

## Analysis

**Time Complexity**: $O(\log n)$**Space Complexity**: $O(\log n)$

# Iterative

Although the complexity of both approaches is identical, but if we use **iteration** instead of **recursion** will be faster in practice since we don’t have the overhead of the recursive calls and reduce the space.

1 | public static double myPow_3(double x, int n) { |

## Analysis

**Time Complexity**: $O(\log n)$**Space Complexity**: $O(\log n)$

All suggestions are welcome.

If you have any query or suggestion please comment below.

Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗