Design recursive algorithms for the following problem Comput

Design recursive algorithms for the following problem:

Compute the n-th power of a number x, x^n, with n non-negative integer. The algorithm should be designed in such a way that it is possible to write a recurrence relation for the total number of multiplications executed by the algorithm for which the Master Theorem applies. Write such a recurrence and apply the Master Theorem to obtain an asymptotic bound for it.

Solution

int power(int x, unsigned int n)
{
int temp;
if( n == 0)
return 1;
temp = power(x, n/2); // calling recursively on half of n
if (n%2 == 0)
return temp*temp;
else
return x*temp*temp;
}

Recurence Relation:
   T(n) = T(n/2) + C , where C is the constants

   comparing this with Master THeorem: T(n) = aT(n/b) + f(n)

   a = 1, b = 2
   logb(a) = log2(1) = 0

   f(n) is constant, c = 0

   so, logb(a) = c =0
   It satisfies the Case 1 of Master Theorem,

   So, Big-O = log(n)