Prove time complexity of recursive algorithm

Question

I have been given a recursive algorithm in an assignment, of which I need to prove it has a given Time Complexity.

The algorithm is as follows (written in Java)

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

}

The assignment is to prove that this algorithm indeed has the time complexity Omega(2^max(n, m)) where n and m are the lengths of w1 and w2 respectively. My knowledge in this area is sparse to say the least but I've managed to find a video on youtube analysing the Fibonacci Sequence recursion pretty helpful.

I've basically tried backwards engineering the solution from the video on my algorithm but I end up with the time complexity Omega(3^min(n, m)).

The way I've reached this conclusion, which is by no means the correct way I'm sure, is that I calculate a kind of a lower bound (I guess?) by saying that T(n-1, m-1) = T(m, n-1) and T(m-1, n) (as I think these are the other two terms). After that I just expand the formula two or three steps and generalize it. I then end up with my above time complexity. I don't understand how the time complexity can be 2^(max(n,m)) as there are 3 additional recursive calls for every one, and I don't understand either why it's max and not min, as the method is linear (right?) when one of the two lengths are zero.

user1196549 · Accepted Answer · 2017-01-26 13:59:55Z

1

The running time must follow the recurrence

T(n, m) = T(n - 1, m - 1) + T(n, m - 1) + T(n - 1, m) + T
T(0, m) = T'
T(n, 0) = T"

A solution with a power of two is unlikely, as a single call involves three indirect calls.

answered Jan 26, 2017 at 13:59

user1196549

Sign up to request clarification or add additional context in comments.

1 Comment

Nyfiken Gul Over a year ago

Thanks for the answer, that's what I thought as well! What are the T' and the T'' notations? And the T in the first row, is that equal to just saying C (a constant value)? Sorry if the questions are dumb, just getting to learn this stuff as of today.

Collectives™ on Stack Overflow

Prove time complexity of recursive algorithm

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related