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.

# Linear algorithm for exponentiation

int power( int x, int n)

{

if(n==0)

return 1;

if(n%2==0)

return power ( x*x , 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)