Home > Algorithms > Java Program for calculating X^n in o(log n ) time complexity

Java Program for calculating X^n in o(log n ) time complexity

November 21, 2011


public class TestMain
{
private static long hits1;
private static long hits2;

public static void main(String[] args)
{
TestMain main = new TestMain();

System.out.println("Normal Result ::"+main.power(2,31));
System.out.println("Hits ::"+hits1);

System.out.println("Optimised Result ::"+main.normalPow(2,31));
System.out.println("Hits ::"+hits2);

}

public long normalPow(long x , long n)
{
long result = 1;

while(n > 0)
{
result = result * x;

n--;

//for calculating hits
hits2++;
}

return result;

}

public long power(long x , long n)
{
//for calculating hits
hits1 ++;
if(n == 0)
{
return 1;
}

long temp = power(x,n/2);
if( n%2 == 0)
{
return (temp * temp );
}else
{
return (temp * temp * x);
}
}
}

Advertisements
Categories: Algorithms
%d bloggers like this: