Even though calculating the exponentiation can be done in linear time of the value of exponent, computation of large integer powers of a number still takes too much time, a better way for fast computation is to make use of binary exponentiation based on the square-and-multiply algorithm.

The key observation in binary exponentiation is that, assume the exponent n is even integer, then to compute xⁿ it is equivalent to (x^n/2)², such recurrence relation can be used to form the recursive algorithm to compute xⁿ for an integer n by using squaring-and-multiplication.

Time Complexity
The time complexity strictly depends on the number of multiplications, since for each recursive step the problem size is reduced by half, so by the master theorem the time complexity is O(log n)

Pseudo Code

pow( x, n )
      if n < 0 then
          return 1 / pow( x, -n );
      else if n == 0 then
          return 1;
      else if n == 1 then
          return x;
      else if n > 1 then
          if n is even then
              tmp = pow( x, n/2 );
              return tmp * tmp;
          else if n is odd then
              tmp = pow( x, (n-1)/2 );
              return tmp * tmp * x;
          end if
      end if