# Algorithm: Pow(n, exp)

Algorithms Math

In this post I will implement basic algorithm to raise floating point number (also known as base) to integer power (also known as exponent). In academic world this process usually referred as Exponentiation. The most naïve implementation is based on the definition of x^{y}, i.e. repetitive y-time multiplication of x.

**Complexity**: O(n).

This implementation can be optimized by using following exponentiation properties:

- b
^{m}= b · b^{m-1} - b
^{m+n}= b^{m}· b^{n} - b
^{m·n}= (b^{m})^{n}In other words, given 2^{7}we can calculate the result as follows:

2^{7} = 2 · 2^{6} = 2 · 2^{2+4} = 2 · 2^{2} · 2^{4} = 2 · 2^{2} · 2^{2·2} = 2 · 2^{2} · (2^{2})^{2}

As you can see, instead of 7 iterations now we have only 3.

**Complexity:** O(log n).