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

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂