By Long Luo

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:

## 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:

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

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$

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

Let’s use recusive in java.

## 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.

## 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. 😉😃💗