-1

I have been given a algorithm about The Levenshtein distance between two character strings and is defined as the minimum number of single-character insertions, deletions, or substitutions (so-called edit operations) required to transform string into string . The algorithm in pseudo code is: enter image description here

I have counted the number of recursive calls which is 3 and number of elements is N - 2 (since function () of the total number ≔ + of input characters). So I got the recurrence as T(N) = 3T(N-2) + dN. But I'm not sure it could be constant d or proportional dN. Using the Master Theorem, I got 2^(N log(3)) with base is 4. I need some help to get the right recurrence for the worst case, and how to determine dN or d. Thank you.``

Sunny Dao
  • 9
  • 1

1 Answers1

0

It is constant.

That part of the formula is not dependent on as the algorithm only needs to access , , [1] and [1] at that stage, so we can just use a constant or even 1 for it (it doesn't matter). The other comparisons that will follow in recursion are covered by the recursive part of the relation.

A few considerations:

  • The recursive part of the formula is not exactly as you say. It is true that the worst case when > 0 and > 0 is when [1] and [1] are different, so we get in the min part of the formula. But there we have two recursive calls that reduce with just 1 (not 2).

  • Simplifying the relation by just using instead of and hides the fact that the recursion will in most cases not continue until is 1, but will abort for some greater value of because at that time a base case kicks in, with =0 or =0. If the purpose is only to find an upper bound for the complexity this is of course not a problem.

See also Calculating the complexity of Levenshtein Edit Distance.

trincot
  • 317,000
  • 35
  • 244
  • 286