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

data-structures runtime big-o trie
Karim Elsheikh picture Karim Elsheikh · Jul 26, 2013 · Viewed 19.4k times · Source

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?

Answer

Alex Brooks picture Alex Brooks · Jul 26, 2013

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.

Related questions

What is the difference between Python's list methods append and extend?

What's the difference between the list methods append() and extend()?

Read More
How to remove a key from a Python dictionary?

When deleting a key from a dictionary, I use: if 'key' in my_dict: del my_dict['key'] Is there a one line way of doing this?

Read More
How do I sort a list of dictionaries by a value of the dictionary?

I have a list of dictionaries and want each item to be sorted by a specific value. Take into consideration the list: [{'name':'Homer', 'age':39}, {'name':'Bart', 'age':10}] When sorted by name, it should become: [{'name':'Bart', 'age':10}, {'name':'Homer', …

Read More