Linear algorithm for exponentiation


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.


int power( int x, int n)
return 1;
return power ( xx , n/2 );
return x * power ( x
x , (n-1)/2 );

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