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.

Question

contestada

Respuesta :

MrRoyal MrRoyal · Answer 1 · 2021-04-25T23:55:08+02:00

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))