Still, trie lookup time is independent from your dictionary size. Sadly, in practice they are hurt by the many pointer dereferences of traversing the tree. If

Still, trie lookup time is independent from your dictionary size. Sadly, in practice they are hurt by the many pointer dereferences of traversing the tree. If you have a sorted list of strings, you can speed up the search by tracking how many starting characters on the left and right boundary of your interval already match the given word. In practice, this turns out to be almost as good as tries as most steps eliminate quite a few characters to check. If you like theory, you can add on Range Minimal Query to get the same theoretical performance as tries. In practice though, this isn't necessary.