# pow(x, y) in O(lgn)

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?).

```//O(lgn)
public static int powRec(int x, int y){
if(y == 0){
return 1;
}
if(y == 1){
return x;
}

int pow = powRec(x, y/2);
if((y&1) != 0){
return pow*pow*x;
}
else{
return pow*pow;
}
}

//O(lgn)
public static int powIter(int x, int y){
int pow = 1;

if(y == 0){
return 1;
}
if(y == 1){
return x;
}

while(y > 0){
//if y is odd
if((y&1) != 0){
pow*=x;
}

//divide by 2
y >>= 1;
//calclate x^2
x = x*x;
}

return pow;
}
```