46

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?

OmG
  • 18,337
  • 10
  • 57
  • 90
Varun
  • 1,159
  • 1
  • 14
  • 19

1 Answers1

64

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.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • 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... – Varun Oct 25 '12 at 04:26
  • 1
    @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. – Sergey Kalinichenko Oct 25 '12 at 04:37
  • wouldnt time complexity for lookups for hastable be O(1)? – lordvcs May 02 '21 at 14:04
  • @lordvcs 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). – Sergey Kalinichenko May 02 '21 at 14:19