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;
}