power function in O(n) time, algorithm plus implementation in python

Algorithm number 1.

 

Algorithm powerOf(x,n)

        Input: integer n, non negative integer x

        Output : x to the power of n

        if n = 0

             return 1

        m ← 0

        while n > 0 do

             m ← m × n

             n ← n – 1

         return m

 

Implementation.

 

def powerOf(x,n):

    if n == 0 : return 1

    m = 0

    while n > 0:

       m *= x

       n -= 1

     return m

 

 

 

Algorithm (recursive) number 2.

 

Algorithm p(x,n)

     Input: integer n, non negative integer x

     Output : x to the power of n

     if n = 0

         return 1

     return x × p(x,n-1)

 

Implementation.

 

def p(x,n):

    if n == 0: return 1

    return x * p(x,n-1)

 

This entry was posted in Code samples and tagged . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *