Временная сложность операции поиска в структуре данных TRIE

Я пытаюсь реализовать структуру данных Trie на основе словаря. Пожалуйста, найдите код Python ниже.

class Trie:
  def __init__(self):
     self.word_end = '_end_'
     self.root = {}  def add_word(self, word):
     self.add_words([word])  def add_words(self, words):
     for word in words:
         current_dict = self.root
         for letter in word:
             current_dict = current_dict.setdefault(letter, {})
         current_dict[self.word_end] = self.word_end  def check_word(self, word):
     current_dict = self.root
     for letter in word:
         if letter in current_dict:
             current_dict = current_dict[letter]
         else:
             return False
     else:
         if self.word_end in current_dict:
             return True
         else:
             return Falsetree = Trie()
tree.add_words(['foo', 'bar', 'baz', 'barz'])
print tree
"""
{'b': {'a': {'r': {'_end_': '_end_', 'z': {'_end_': '_end_'}}, 
             'z': {'_end_': '_end_'}}}, 
 'f': {'o': {'o': {'_end_': '_end_'}}}}
 """print check_word('baz')
# True
print check_word('barz')
# True
print check_worf('barzz')
# False

Я вижу сложность поиска слова O (m), где m - длина слова, которое ищется. Кроме того, добавление слова имеет очень похожую сложность - O (m), где m - длина добавляемого слова.

Вопрос: Эти сложности слишком хороши. Может кто-нибудь подтвердить эти сложности? Что-то не так в моей реализации Trie?