Friday, February 25, 2011

Java program to calculates x^m in O(log m) time

public int logpower(int x,int m)
{
//Calculates x^m in O(log m) time

if(m==1)
return x;
else if(m%2!=0)
return logpower(x,m/2)*logpower(x,m/2)*x;
else
return logpower(x,m/2)*logpower(x,m/2);
}
Posted by at

1 comment:

Srikkanth said...

Hi,

This algorithm takes more than log m times because the number of recursive invocations are doubled everytime.

i.e for logpower(2,8) - it will call logpower(2,4) - 2 times
logpower(2,2) - 4 times
logpower(2,1) - 8 times

Actually for log m complexity, the recursive call should be made only once. i.e instead of
logpower(x,m/2) * logpower(x,m/2)..it should be

int power = logpower(x,m/2);
int result = power * power //even no

May 25, 2011 at 8:08 PM

Post a Comment

Subscribe to: Post Comments (Atom)