Problem 3
The function distance returns the distance between two
strings X and Y. Its running time is exponential. Explain why.
(Note: make sure you understand what X[0: -1] is.)
#
# Input: X, Y, which are strings
# Output: a number, which is the distance between the two strings
#
def distance(X, Y):
if len(X)==0:
return len(Y)
if len(Y)==0:
return len(X)
if X[-1]==Y[-1]:
return distance(X[0:-1], Y[0:-1])
else:
a = distance(X[0:-1], Y[0:-1])
b = distance(X, Y[0:-1])
c = distance(X[0:-1], Y)...