"Isn't that O(Nk), where k is the average word length and N is the number of words. Given an upper bound on k, this is no worse than a trie."Let's make an even stronger assumption that every word in your set has length k. You then need to store (k^2 + k)/2 characters per distinct word with the sorted set implementation (plus any additional data-structure overhead). In a worst-case scenario, you have N of these k-length words, distinct at the first character (this might seem paranoid for something like ASCII, but think about Unicode here...or just change the problem to N distinct strings at character >=2), resulting in a worst-case memory bound of O(N * ((k^2 + k) / 2)).
That said, the possible range of N will be much larger than k for any non-trivial k, so I suppose it's fair to say that real-world memory use is something more like O(N) with a very high constant that's quadratically related to your average word length. But that's still substantially worse than a well-implemented trie (where your constant is small and unrelated to k), and with large data sets every byte counts.
"Although the top 1000 recently searched items might not share as much structure, that is a trivial amount of data, even for O(N^2)....the storage overhead on a trie is high, especially as many bigrams don't occur in English, so array-based tries necessarily waste space."
If your set size is only 1,000, then yeah, this conversation is academic. I'm talking about big suggestion sets -- for a website, it's not too difficult to get into a situation where your suggestion set is in the hundreds of thousands or millions of strings or more. Remember that web text is nothing like /usr/share/dict. Proper nouns, acronyms, non-words, new words, foreign words, etc. all conspire to make real-world language much larger and more diverse than the system dictionary. The size of real-world vocabularies is one of those counter-intuitive things that I wouldn't have guessed before working on websites.
Finally, while you definitely have to be careful when implementing a trie, there are improved trie algorithms (like burst tries), that greatly improve upon average- and worst-case memory usage. A totally naïve trie implementation has a ton of overhead...but then, a naïve set implementation has a ton of overhead, too. So it's important to not be naïve. ;-)
(related: looks like the redis guys have been oddly resistant to adding tries, despite several requests: https://code.google.com/p/redis/issues/detail?id=110)