# Efficiently implement power function | Recursive and Iterative

Given two integers x and n where n is non-negative, efficiently compute the value of power function pow(x, n).

For example,

pow(-2,10) = 1024
pow(-3,4) = 81
pow(5,0) = 1
pow(-2,3) = -8

### 1. Naive iterative solution–

A simple solution to calculate pow(x, n) would be multiply x exactly n times. We can do that by using simple for loop.

## Java

Output:

pow(-2,10) = 1024

The time complexity of above solution is O(n).

### 2. Using Divide & Conquer –

We can recursively define the problem as –

power(x, n) = power(x, n / 2) * power(x, n / 2);        // else n is even
power(x, n) = x * power(x, n / 2) * power(x, n / 2);   // if n is odd

## Java

Output:

pow(-2, 10) = 1024

The time complexity of above solution is O(n).

### 3. Optimized Divide & Conquer solution –

The problem with above solution is that same sub-problem is getting computed twice for each recursive call. We can optimize the above function by computing the solution of sub-problem once only.

## Java

Output:

pow(-2,10) = 1024

The time complexity of above solution is O(log(n)).

### 4. Using Low Level Programming (Binary operators) –

We can also use binary operators to compute pow(x, n) in O(log(n)) time.

## Java

Output:

pow(-2,10) = 1024

The time complexity of above solution is O(log(n)).

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Get great deals at Amazon