# Power(base, exponent)by Isai Damier, Android Engineer @ Google

```#======================================================================
# Author: Isai Damier
# Title: Power(base, exponent)
# Project: geekviewpoint
# Package: algorithms
#
# Statement: Compute base x raised to exponent n: x^n
#
# Sample Input: 3^11
# Sample Output: 177147
#
# Time Complexity of Solution:
#   Best = Average = Worst = O(Time) = O(log n),
#
# Technical Details:
#   Instead of multiplying x by itself n times using a for-loop,
#   we continually divide the exponent by two (think binary search)
#   hence reducing the time complexity to O(log n) instead of O(n).
#   We demonstrate by manually solving for 3^11.
#
#   3^11 = 3^5 * 3^5 * 3
#   3^5 = 3^2 * 3^2 * 3
#   3^2 = 3 * 3 = 9
#
#  Therefore, we perform five multiplications instead of eleven:
#  3*3=9; 993 = 243; 243*243*3 = 177147
#======================================================================
def pow( base, exponent ):
if 1 == exponent:
return base

result = pow( base, exponent / 2 )
if 0 == ( exponent & 1 ):
return result * result
return result * result * base```
```import unittest
from algorithms import numbers as algorithm

class Test( unittest.TestCase ):

def testPow( self ):
x = 2;
n = 11;
self.assertEquals( int ( x ** n ), algorithm.pow( x, n ) )
x = 3
n = 7
self.assertEquals( int ( x ** n ), algorithm.pow( x, n ) )
x = 5
n = 4
self.assertEquals( int ( x ** n ), algorithm.pow( x, n ) )
x = 4
n = 6
self.assertEquals( int ( x ** n ), algorithm.pow( x, n ) )
```