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”, that’s just three steps.

Expressing trie search in terms of Big O is slightly tricky. We can’t quite call it O(1), since the number of steps isn’t constant, as it all depends on the search string’s length. And O(N) can be misleading, since N normally refers to the amount of data in the data structure. This would be the number of nodes in our trie, which is a much greater number than the number of characters in our search string.

Most references have decided to call this O(K), where K is the number of characters in our search string. Any letter other than N would have worked here, but K it is.

Even though O(K) isn’t constant, as the size of the search string can vary, O(K) is similar to constant time in one important sense. Most non-constant algorithms are tied to the amount of data at hand; that is, as N data increases, the algorithm slows down. With an O(K) algorithm, though, our trie can grow tremendously, but that will have no effect on the speed of our search. An O(K) algorithm on a string of three characters will always take three steps, no matter how large the trie is. The only factor that affects our algorithm’s speed is the size of our input rather than all the available data. This makes our O(K) algorithm extremely efficient.

While search is the most common type of operation performed on tries, it’s difficult to test drive it without populating our trie with data, so let’s tackle insertion next.