Menu
What is the best/worst/average case complexity (in Big-O notation) of a trie data structure for insertion and search?
I think it is O(K) for all cases, where K is the length of an arbitrary string which is being inserted or searched. Will someone confirm this?
461
The time complexity for building a Trie data structure is O(N * avgL), where 'N' is the number of strings we want to insert in Trie and 'avgL' is the average length of 'N' strings. Trie data structure has many applications, including 'prefix-based searching', 'sorting strings lexicographically' etc.
The worst-case runtime for creating a trie is a combination of m, the length of the longest key in the trie, and n, the total number of keys in the trie. Thus, the worst case runtime of creating a trie is O(mn).
Best case is the function which performs the minimum number of steps on input data of n elements. Worst case is the function which performs the maximum number of steps on input data of size n. Average case is the function which performs an average number of steps on input data of n elements.
9. Which of the following is true about the trie? Explanation: A trie is an ordered tree where (i) the root represents an empty string(“”) (ii) each node other than root is labeled with a character (iii) the children of a nodes are lexicographically ordered (iv) the paths from the leaves to the root yields the strings.
According to Wikipedia and this source, the worst case complexity for insertion and search for a trie is O(M) where M is the length of a key. I'm failing to find any sources describing the best or average case complexity of insertion and search. However, we can safely say that best and average case complexity is O(M) where M is the length of a key, since Big-O only describes an upper bound on complexity.
102
k: the length of the string that you search or insert.
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'.
Trie's complexity does not change with the number of strings that you search, only with search string's length. That's why Trie is used when the number of strings to search is large, like searching the whole vocabularies in an English dictionary.
For Insertion
Worst: O(26*k) = O(k)
Average: O(k)
Best: O(1)
So, yes, you are right. You would probably have seen O(MN) and that might have confused you but it's simply talking about when you need to do above O(k) operations N times.
44
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
