CODEWITHSUNDEEP
algorithmrecursiontime-complexity
hampusohlsson
hampusohlsson

Reputation: 10219

Find time complexity of recursive function

Assignment is to show that the time complexity is Ω(2max(n,m)) in the worst case scenario for following recursive function.

Assume the following:

Here is the code

int dist(String w1, String w2, int w1len, int w2len) {
    if (w1len == 0) {
        return w2len;
    }
    if (w2len == 0) {
        return w1len;
    }   
    int res = dist(w1, w2, w1len - 1, w2len - 1) + (w1.charAt(w1len - 1) == w2.charAt(w2len - 1) ? 0 : 1);      
    int addLetter = dist(w1, w2, w1len - 1, w2len) + 1;
    if (addLetter < res)
        res = addLetter;
    int deleteLetter = dist(w1, w2, w1len, w2len - 1) + 1;
    if (deleteLetter < res)
        res = deleteLetter;

    return res;
}

Upvotes: 1

Views: 1257

Answers (1)

MK.
MK.

Reputation: 34537

Try to draw call tree for the function. What does it look like? Can you estimate the number of invocation of dist function?

Upvotes: 1

Related Questions