check your skill in basic algorithm analysis!!

one of the basic algorithms has been the exponentiation.

Exponentiation
This involves raising an integer to a power (which is also an integer).
The obvious algorithm to compute X^N uses N-1 multiplications.
In this section we shall see a better algorithm compared to the above one.


Efficient Exponentiation

long int pow(long int X, unsigned int N)

{

/* 1 */ if(N==0)

/* 2 */ return 1;

/* 3 */ else if(N==1)

/* 4 */ return X;

/* 5 */ else if(isEven(N))

/* 6 */ return pow( X * X, N /2);

else

/* 7 */ return pow( X * X, N /2)*X;

}


Analysis

Lines 1 to 4 handle the base case of recursion. Otherwise

if N is even , we have X^N = X^N/2 * X^N/2

and if N is odd, we have X^N= X^(N-1)/2 * X^(N-1)/2


The number of multiplications required is clearly at most 2 log N, because at most 2 multiplications are required(if N is odd) to halve the problem.

Simple intuition obviates the need for a brute-force approach.

one of the following alternative lines for line 6 are bad, even though they look correct:

/* 6a */ return pow( pow( X,2) , N/2);



/* 6b */ return pow( pow( X,N/2) , 2);



/* 6c */ return pow(X,N/2) * pow(X,N/2);

guess why??


Both lines 6a and 6b are incorrect because when N is 2, one of the recursive calls to pow has 2 as the second argument.Thus no progress is made, and an infinite loop results in an eventual crash.

Using line 6c effects the efficiency, because there are now 2 recursive calls of size N/2 instead of one.