[7급 국가직 자료구조론 2014년 3번]

다음은 xⁿ을 구하는 알고리즘이다. 이 알고리즘의 시간 복잡도는? (단, n > 0이며, even(m)은 m이 짝수일 때 참을 반환하고 그렇지 않을 때 거짓을 반환하는 함수이다)

int PowersRec(int x, int n) 
{
   int Pow;
   if (n == 1)
      Pow = x;
   else {
      if (even(n))
         Pow = PowersRec(x*x, n/2);
      else
         Pow = x * PowersRec(x*x, (n-1)/2);
   }
   return (Pow);
}