Эффективность словарей на Python:

В рекурсивной функции ниже я применил некоторые методы мемоизации в python для сохранения предыдущих вычисленных значений в словаре, который теоретически должен иметь сохранение и извлечение O (1). Однако время выполнения примерно в три раза больше при использовании мемоизации, чем при простой рекурсии.

В двух частях приведенного ниже кода, какова возможная причина такого более длительного времени выполнения во втором коде? Я неправильно использую словари?

Простая рекурсивная функция:

import time

def deletion_distance(str1, str2):
  if str1 is "":
    return len(str2)
  elif str2 is "":
    return len(str1)
  else:
    if str1[len(str1) - 1] == str2[len(str2) - 1]:
      return deletion_distance(str1[:-1],str2[:-1])
    else:
      return 1 + min(deletion_distance(str1, str2[:-1]),deletion_distance(str1[:-1],str2))

str1 = "dragonified"
str2 = "infinitezimal"

start = time.time()
for i in range(0,2):
    deletion_distance(str1,str2)
end = time.time()

print((end - start) / 2)

Динамическое программирование с использованием словарей для мемоизации:

import time

def deletion_distance(str1, str2):
  global aux_dict

  if str1 is "":
    return len(str2)
  elif str2 is "":
    return len(str1)
  else:
    if str1[len(str1) - 1] == str2[len(str2) - 1]:
      if "1"+str1[:-1]+"2"+str2[:-1] in aux_dict:
        return aux_dict["1"+str1[:-1]+"2"+str2[:-1]]
      else:
        aux_dict["1"+str1[:-1]+"2"+str2[:-1]] = deletion_distance(str1[:-1],str2[:-1])
        return aux_dict["1"+str1[:-1]+"2"+str2[:-1]]
    else:

      return 1 + min(
        aux_dict["1"+str1+"2"+str2[:-1]] if "1"+str1+"2"+str2[:-1] in aux_dict else deletion_distance(str1, str2[:-1]),
        aux_dict["1"+str1[:-1]+"2"+str2] if "1"+str1[:-1]+"2"+str2 in aux_dict else deletion_distance(str1[:-1],str2))

aux_dict = {}      
str1 = "dragonified"
str2 = "infinitezimal"

start = time.time()
for i in range(0,2):
    deletion_distance(str1,str2)
end = time.time()

print((end - start) / 2)

Обе функции вычисляют расстояние удаления двух строк (вопрос PRAMP.COM), которое представляет собой просто минимальное количество символов обеих строк, которое необходимо удалить из двух строк, чтобы они стали одинаковыми.