Linear algorithm for exponentiation


#1

The obvious linear algorithm for exponentiation x^n uses n-1 multiplications . propose a faster algorithm and find its Big-oh complexity in the case when n=2^m by writing and solving a recurrence formula.


#2

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

The complexity of above algorithm is O ( log n ) = O (log 2^m) = O (m)