Trie

Why it costs this much

Each step follows one child per character, so the work depends on the word length and not on how many words are stored.

Code

def insert(root, word):          # root = {}
    node = root
    for ch in word:                       # m steps for a word of length m
        node = node.setdefault(ch, {})    # O(1) expected per character
    node["$"] = True                      # end-of-word marker

Common pitfalls

Memory can be large because each node may hold many child pointers. Hash-map children save space at some cost in speed.

Operation by operation

Trie insert and search. m is the length of the key. Children stored in arrays or hash maps. Independent of the number of stored keys, but can use a lot of memory.