# yaox023's blog # Fast Power Algorithm

There is a leetcode problem Pow(x, n). Basically, it is a plain power function.

We can follow the description and multiple number x with n times.

``````function myPow(x: number, n: number): number {
// for negative n, we need to do a 1/x operation
if (n < 0) {
n = -1 * n;
x = 1 / x;
}

let ans = 1;
for (let i = 0; i < n; i++) {
ans *= x;
}
return ans;
};
``````

As you can see, in this way, the time complexity is `O(n)`.

We can use a divide and conquer approach to make the time complexity `O(log(n))`.

The idea behind this algorithm is based on the ideas below.

If number n is even, then we can have:

``````x^n = x^(n/2) * x^(n/2)
``````

So with this idea, we can calculate `x^n` with only `n/2+1` multiplication operations, instead of `n` times. (Suppose we do `x^(n/2)` with the brute-force approach).

If number n is odd, we can just minus 1 to make it even:

``````n = n - 1
x^n = x^(n/2) * x^(n/2) * x
``````

So with this simple idea, let's see it in code.

``````function myPow(x: number, n: number): number {
if (n < 0) {
n = -1 * n;
x = 1 / x;
}

if (n === 0) return 1;

if (n % 2 === 0) {
const v = myPow(x, n / 2);
return v * v;
} else {
const v = myPow(x, (n-1) / 2);
return v * v * x;
}
};
``````