Powering a Number

Problem Statement:

Given a number X and an integer n, n>=0.
Compute: power(X,n)

Naive Algorithm:

Naive algorithm would involve multiplying X, n times.
X*X*X ….. n times

Time Complexity: O(n)

Now, lets look at a more efiicient way of doing this algorithm

Divide and Conquer:

Idea:

Power(X,n) = Power(X,n/2)* Power(X,n/2)  ................ if n is even
           = Power(X,n-1/2)*Power(X,n-1/2)*X ........ if n is odd

Implementation:
The following function will do the needful.

Lets look at the recurrence:

public static int power(int x, int n) {
     if(n == 0)
         return 1;
    else if(n==1)
          return x;
    else if(n%2==0) {
          int y = power(x,n/2);
          return y*y;
    }else {
          int y = power(x,n-1/2);
          return y*y*x;
    }
}

 

T(n) = T(n/2) + O(1)
Because, i am dividing the problem into halves(ok not exactly halves, but since we r using Big-Oh notation, i can be sloppy). Also, the time to conquer is constant as it involves atmost 2 multiplications.

So, the following recurrence drills down to: O(log n)

Which is way better than linear time!