What is the best / worst / average O-Trie runtime for a large number of records?

Question

What is the best / worst / average complexity of the case (in Big-O notation) of the trie data structure for insert and search?

I think this is O(K) for all cases where K is the length of an arbitrary string that is inserted or searched. Anyone confirm this?

Answer 1

According to Wikipedia and this source , the worst difficulty to insert and search for trie is O(M) , where M is the key length. I can’t find sources describing the best or average complexity of typing and searching. However, we can confidently say that the best and average complexity of the case is O(M) , where M is the key length, since Big-O describes only the upper bound of complexity.

Answer 2

k: the length of the string you are looking for or inserting.

 For Search Worst: O(26*k) = O(k) Average: O(k) # In this case, k is an average length of the string Best: O(1) # Your string is just 'a'. 

The complexity of Trie does not change with the number of lines you are looking for, only with the length of the search string. This is why Trie is used when the number of lines to search is large, for example, searching for all dictionaries in an English dictionary.

 For Insertion Worst: O(26*k) = O(k) Average: O(k) Best: O(1) 

So yes, you are right. You probably saw O (MN), and that may have confused you, but it just says when you need to perform O (k) operations N times.

Answer 3

Wikpedia has great info on this. http://en.wikipedia.org/wiki/Trie