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 our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of