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.

C

Download   Run Code

Java

Download   Run Code

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

C

Download   Run Code

Java

Download   Run Code

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.

C

Download   Run Code

Java

Download   Run Code

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.

C

Download   Run Code

Java

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 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of