contestada

An alternative strategy for the expo function uses the following recursive definition: expo(number, exponent) = 1, when exponent = 0 = number * expo(number, exponent – 1), when exponent is odd = (expo(number, exponent // 2)) ** 2, when exponent is even Define a recursive function expo that uses this strategy, and state its computational complexity using big O notation.

Respuesta :

MrRoyal

Answer:

The recursive function in Python is as follows

def expo(nmber, exponent):

   power = exponent

   if power == 0:

       return 1

   if power %2 == 1:

       power = power - 1

       return nmber * expo(nmber, power)

   else:

       power = power/2

       return expo(nmber, power) ** 2

The time complexity is O(log(n))

Step-by-step explanation:

See attachment for complete program where comments are used for explanation.

The Time Complexity

The function is then called power - 1 times for odd exponents or power/2 times for even exponents before it reaches the base case.

As the exponent is divided by 2, for even exponents; it means that the function tends to log(n). log(n), in this case represents the base case.

Since the function is repeated, then the time complexity is: O(log(n))

Ver imagen MrRoyal

Otras preguntas