A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

The Efficiency of Trie Search

The great thing about trie search is that it’s incredibly efficient.

Let’s analyze the number of steps it takes.

In our algorithm, we focus on each character of our search string one at a time. As we do so, we use each node’s hash table to find the appropriate child node in one step. As you know, a hash table lookup takes just O(1) time. It turns out, then, that our algorithm takes as many steps as there are characters in our search string.

This can be much faster than using binary search on an ordered array. Binary search is O(log N), with N being the number of words in our dictionary. Trie search, on the other hand, takes only as many steps as the number of characters in our search term. For a word like “cat”, ...