Powering a Number in O(logn) Time.

Problem:Compute a^n, where n is a natural number.
Naive algorithm:Θ(n).
a^n = a^(n/2) * a^(n/2) if n is even;
= a^((n–1)/2) * a^((n–1)/2) * a if n is odd;


Divide-and-conquer algorithm:
T(n) = T(n/2) + Θ(1) ⇒T(n) = Θ(lgn).


Input:
15
7
Output:
15^7 = 170859375


Code: