Exponentiation is raising a number to a power (represented as x^{n}).

Assuming n>=0

**Naive method to calculate x**^{n}int exponentiate(int x, int n) { int result=1; for(int i=1; i<=n; i++) { result=result*x; } return result; }

The above code takes O(n) time to compute x

^{n}**Exponentiation by squaring**

There exists another method to calculate x^{n}in O(log n).It is evident that

x

^{n}= x^{n/2}*x^{n/2}*x if x is oddx

^{n}= x^{n/2}*x^{n/2}if x is evenWe can use this fact to calculate x

^{n}in O(log n) time.int exponentiate(int x, int n) { static int result; if(n==0) { return 1; } if(n%2==1) { result=exponentiate(x, n/2); result=result*result*x; } else { result=exponentiate(x, n/2); result=result*result; } return result; }

Complexity of above code is O(log n).

Advertisements