Implement pow(x,y) in logarithm time
The problem would be straightforward if we are allowed to do it in O(n) time as we can simply multiple x by itself y times. But how to do it in log time?
The problem description itself is telling us how to implement it in log time. If we need to find power of x raised to y in logarithmic time then somehow we need to make the computation tree into half in each iteration. For example, a^5 = a^2*a^2*a. a^10 = a^5*a^5. So, basically if we can compute a^(y/2) once then we use this computation to find a^y by simply multiplying the result to itself if y is even. If y is odd then we need to multiply x once more with the even multiplication result. Below is the implementation of this idea in both recursive and iterative approach. Both code runs in O(lgn) time (why?).