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);
}
at

1 comment:

  1. SrikkanthMay 25, 2011 at 8:08 PM

    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

    ReplyDelete