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 power ( xx , n/2 );
return x * power ( xx , (n-1)/2 );
The complexity of above algorithm is O ( log n ) = O (log 2^m) = O (m)