python - 再帰的アナグラムアルゴリズムのBigOの複雑さ

Question

再帰メソッドanagram（）を使用して、文字列のすべての順列を返そうとしています。「ABCD...N」という単語の場合、この関数は、anagram（ "BCD ... N"）内のできるだけ多くの位置に文字「A」が含まれるリストを返します。再帰の限定的なケースは、引数のサイズが2（例： "XY"）の場合、['XY'、'YX']を返すことです。

コードは次のとおりです。

def anagram(block):
   if (len(block) <= 2):
      permu=list()
      permu.append(block[0]+block[1])
      permu.append(block[1]+block[0])
   else:
      permu=list()
      lowerpermu=anagram(block[1:])             # anag(sd)
      for blocklet in lowerpermu:           # sd, ds are blocklets
         for each in rotate(block[0],blocklet):     # each in ['asd', 'sad', 'sda'] and ['ads', 'das', 'dsa']
            permu.append(each)
   return permu


def rotate(letter, word):
   rotatedlist=list()
   for i in range(len(word)+1):
      rotatedlist.append(word[:i]+letter+word[i:])
   return rotatedlist

def main():
   word=raw_input('Enter the word to be anagrammed: ')  #for example: 'asd'
   print anagram(word)                  

if __name__ == '__main__':
    main()

私は自分自身に一般的なアルゴリズムとその分析を教えています。再帰が関係するアルゴリズムの順序を推定するための経験則の方法を誰かが提案してくれれば幸いです。