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


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.

C++ implementation –
 

Download   Run Code

Output:

pow(-2,10) = 1024

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

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

 
C++ implementation –
 

Download   Run Code

Output:

pow(-2, 10) = 1024

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

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.

C++ implementation –
 

Download   Run Code

Output:

pow(-2,10) = 1024

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

Using Low Level Programming (Binary operators) –

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

C++ implementation –
 

Download   Run Code

Output:

pow(-2,10) = 1024

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

Thanks for reading.




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 🙂