What is the Best/Worst/Average Case Big-O Runtime of a Trie Data Structure?

Question

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?

Solution 1

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.

Solution 2

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.

Comments

[Heye]

"Best" is still O(k) because in case of just 'a' (a.k.a. a string with length 1), the value of k is 1