Finding Power of a Number in O(log(n)) using Java

By Lokeswara Reddy Ajjuguttu

In this Java post, we will be discussing how to find power of a given number. This approach will be more efficient. In this approach will be using a O(log(n)) time complexity algorithm.

Power of a number A^B is the product of A, B times i.e..

A^B = A*A*A*A*......(B times).

In this post we will be discussing two methods to find power of given number.

Approach 1:

1. Take the input values of A and B.

2. To retain the values of A and B let us store them in another variables named X and n. And take a variable result which is initialized to 1.

3. Now, iterate a loop till n value reaches to 0(zero).

4. For each iteration in n multiply result with X and reduce the value of n by 1.

5. Finally if n value reaches to zero then we stop this process and then return the result.

int n=B;
int X=A;
int result=1;
while(n>0){
    result*=X;
    n=n-1;
}

Complexity Analysis:

Time Complexity: O(n). As, we are just iterating the loop just n(=B) times.

Space Complexity: O(1).

Approach 2: In this approach we just use a simple Math logic.

If n value is Even  then we multiply the value of X with itself and reduce the value of n to its half here.

Example: A^B  =  A^2(B/2)  =  (A * A)^B/2  (when B value is Even).

When B value is 1 (Odd)  then we multiply the result with the value of X. 

1. Take the input values of A and B.

2. To retain the values of A and B let us store them in another variables named X and n. And take a variable result which is initialized to 1.

3. Now, iterate a loop till n value reaches to 0(zero).

4. For each iteration if n value is Even then we multiply X with itself then we reduce the value of n to its half.

5. And if when n value is odd then we multiply result with X value and then we reduce the value of n by 1.

6. Finally if n value reaches to zero then we return the result.

 

Complexity Analysis:

Time Complexity: O(log(n)) . Here, we are reducing the value of n to its half. So, we are just iterating the loop by n value. So, time Complexity is reduced to O(log(n)) from O(n). 

Space Complexity: O(1)

As we are not using any extra space.