Menu
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?
913
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.
A trie is a data structure used for efficient retrieval of data associated with keys. If key is of length n, then using trie worst case time complexity for searching the record associated with this key is O(n).
A Trie is a data structure designed for quick reTRIEval of objects by string search. This was designed for use with a type-ahead search (e.g. like a dropdown) but could be used in a variety of situations.
The trie solution is more flexible to support more applications, such as auto-complete. Also, we can easily print all the words in the dictionary in alphabetic order with a trie. Therefore, if we want a full-text lookup application, the hash table is better as it has a faster lookup speed.
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.
128
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
