Answer:
The algorithm is as follows:
Exponent(x, n):
if(n == 0):
return 1
pr = Exponent(x, int(n / 2))
if (n % 2 == 0):
Return pr* pr
else:
if(n > 0):
Return x * pr* pr
else:
Return (pr* pr) / x
Explanation:
In order to get a O(log n) time complexity, a recursive procedure is implemented by the algorithm
The algorithm begins here
Exponent(x, n):
If n is 0, the procedure returns 1
if(n == 0):
return 1
This recursively calculates the product of x, n/2 times
pr= Exponent(x, int(n / 2))
If n is even, the square of prod (above) is calculated
if (n % 2 == 0):
Return pr* pr
If otherwise (i.e. odd)
else:
If n is above 0, the square of prod multiplied by x is calculated
if(n > 0):
Return x * pr* pr
If otherwise, the square of prod divide by x is calculated
else:
Return ([tex]pr* pr[/tex]) / x
The time complexity is: O(log|n|)
