Question

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)

        return 1 + min(a,b,c)

Answer 1

Lets Suppose Length of String argument given to function intially are

For String x = n

String y = m

X[-1] = last character of string X = X[n-1]

X[0:-1] = String after removing X[n-1](X[-1] or last character of string) from String X , so length of X[0:-1] will be (n-1)

distance(x,y)

Base case (termination) for function is when length of one of the argumen is 0;

else

/*

 else:

        a = distance(X[0:-1], Y[0:-1])

        b = distance(X, Y[0:-1])

        c = distance(X[0:-1], Y)

        return 1 + min(a,b,c)

It will be calling 3 more function with aregument (n-1,m-1) (n,m-1) (n-1,m) respectively

*/

if (X[-1] == Y[-1])

then function is making call to one function , we are ignoring matching of last character of string to calculate worst case time complexity of function

following is tree to calculate total number of calls made in one execution of program

So programs complexity will O(3ⁿ) which is exponential.