Work with recursion and BigO notation This problem considers

Work with recursion and Big-O notation

This problem considers several ways to compute x^n for integers x and n greaterthanorequalto 0. Write an iterative function power1 to compute x^n for n greaterthanorequalto 0. Write a recursive function power2 to compute x^n by using the following recursive formulation: x^0 = 1 x^n = x * x^n - 1 if n > 0 Write a recursive function power3 to compute x^n by using the following recursive formulation: x^0 = 1 x^n = (x^n/2)^2 if n > 0 and n is even x^n = x * (x^(n - 1)/2)^2 if n > 0 and n is odd Make only one recursive call each time through the function, so that it operates efficiently. What is the running time of each of the above algorithms as function of n? Use Big-O notation and justify your answer.

Solution

a.

def power1(x, n):
   res = 1

     for i in range(n):
   res *= x
   return res

Time complexity: O (n)

Ans.b.

def power2(x, n):
   if n == 0:
   return 1
   else:
   return x * power2(x, n - 1)
Time complexity: O(n)

Ans. c.

def power3(x, n):
   if n == 0:
   return 1
   elif n%2 == 0:
res = power3(x, n/2)
   return res * res
   elif n%2 == 1:
     res = power3(x, (n - 1)/2)
   return res * res * x

Time complexity: O(log n)