Trie complexity and searching
algorithm, data-structures, hashtable, time-complexity, trie
Solution
The complexity of creating a trie is `O(W*L)`, where `W` is the number of words, and `L` is an average length of the word: you need to perform `L` lookups on the average for each of the `W` words in the set.
Same goes for looking up words later: you perform `L` steps for each of the `W` words.
Hash insertions and lookups have the same complexity: for each word you need to check equality, which takes `O(L)`, for the overall complexity of `O(W*L)`.
If you need to look up entire words, hash table is easier. However, you cannot look up words by their prefix using a hash table; If prefix-based lookups are of no interest to you, use a hash table; otherwise, use a trie.
Problem
What is the complexity of creating a trie of a list of words and what is complexity of searching other set of word in that trie? Should I use trie for string searching, when i have hashtable?