Algorithm and Complexity, Python

Task 1a) Write a program to test and compare the time used for exponentiation by expt, it_exp and better_exp on your system.

b) Estimate the complexity of all the functions.

def it_exp(b, n):

return exp_it(b, n, 1)

def exp_it(b, count, prod):

if count == 0:

return prod

else:

return exp_it(b, count - 1, b*prod)

def square(x):

return x*x

def better_exp(b, n):

if n == 0:

return 1

elif (n % 2 == 0):

return square(better_exp(b, n // 2))

else:

return b*better_exp(b, n-1)

[] def it_exp(b, n): return exp_it(b, n, 1) def exp_it(b, count, prod): if count == 0: return prod else: return exp_it(b, count - 1, b*prod) it_exp(2, 3) 8 [] def square(x): return x x def better_exp(b, n): if n == 0: return 1 elif (n % 2 == 0): return square(better_exp(b, n // 2)) else: return b*better_exp(b, n-1) [] better_exp(2, 3) 8 [] # Task 1a) Write a program to test and compare time used for exponentiation by expt, it_exp and better_exp on your system. b) Estimate the complexity of all of the above functions. #