Trie complexity and searching

Question

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?

Flatting

Answer 1

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.

Danley

if i am looking up the entire word in hashtable ,I need some good hash function and its we should be little careful when defining the hash function. Correct me if i m wrong... – Flatting

@var Because of widespread use of strings as keys of hash tables, very good hashing functions for strings have been invented. A quick search on the internet would give you a half dozen excellent suggestions. I would go with the one Microsoft uses, or the one built into Java strings, because they have been optimized a lot. – Danley

wouldnt time complexity for lookups for hastable be O(1)? – Cacuminal

@Cacuminal This is true only if you consider the length of the string to be fixed, or to have a fixed upper limit, i.e. when you treat L as a constant, not a variable. The context of this question does not allow you to do so, because trie is sensitive to the length of the string (it influences the height of the trie). – Danley