CODEWITHSUNDEEP
data-structuresruntimebig-otrie
Karim Elsheikh
Karim Elsheikh

Reputation: 349

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

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?

Upvotes: 16

Views: 28998

Answers (4)

Shahzeb Naveed
Shahzeb Naveed

Reputation: 52

The best case for Search will be when the word being looked up is not present in the trie so you'll know right away yielding the best-case run-time of O(1). For insertion, best-case remains O(n) as you're either doing successful look-ups or creating new nodes for all the letters in the word.

Upvotes: -1

aerin
aerin

Reputation: 22724

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.

Upvotes: 8

Alex Brooks
Alex Brooks

Reputation: 1151

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.

Upvotes: 19

Ralph Caraveo
Ralph Caraveo

Reputation: 10225

There is some great info about this on Wikpedia. http://en.wikipedia.org/wiki/Trie

Upvotes: 0

Related Questions