algorithm - 編集距離（レーベンシュタイン距離）再帰トップダウン実装の複雑さ

Question

私は一日中、対処できないような問題に取り組んできました。タスクは、編集距離の再帰的実装が時間計算量Ω（2 ^{max（n、m）}）を持っていることを示すことです。ここで、n＆mは測定される単語の長さです。

実装はこの小さなPythonの例に匹敵します

def lev(a, b):
    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)

差出人：http ：//www.clear.rice.edu/comp130/12spring/editdist/

さまざまな短い単語に対して再帰の深さのツリーを描画しようとしましたが、ツリーの深さと複雑さの関係を見つけることができません。

私の計算からの再帰式

m = length of word1
n = length of word2
T(m,n) = T(m-1,n-1) + 1 + T(m-1,n) + T(m,n-1)
With the base cases:
T(0,n) = n
T(m,0) = m

しかし、長さが0に達しないため、各呼び出しは3つの新しい呼び出しにつながるため、どのように進めるかはわかりません。

下限の複雑さがΩ（^{2max（n、m）}）であることを示すためにどのように進めることができるかについてのヒントをいただければ幸いです。