title: Calculating the complexity of Levenshtein Edit Distance
body: <p>I have been looking at this simple python implementation of <a href="http://en.wikipedia.org/wiki/Levenshtein_distance" rel="nofollow">Levenshtein Edit Distance</a> for all day now.</p>
  
  <pre><code>def lev(a, b):
      """Recursively calculate the Levenshtein edit distance between two strings, a and b.
      Returns the edit distance.
      """
      if("" == a):
          return len(b)   # returns if a is an empty string
      if("" == b):
          return len(a)   # returns if b is an empty string
      return min(lev(a[:-1], b[:-1])+(a[-1] != b[-1]), lev(a[:-1], b)+1, lev(a, b[:-1])+1)
  </code></pre>
  
  <p>From: <a href="http://www.clear.rice.edu/comp130/12spring/editdist/" rel="nofollow">http://www.clear.rice.edu/comp130/12spring/editdist/</a></p>
  
  <p>I know it has an exponential complexity, but how would I proceed to calculate that complexity from scratch?</p>
  
  <p>I have been searching all over the internet but haven't found any explainations only statements that it is exponential.</p>
  
  <p>Thanks.</p>