What is the Best/Worst/Average Case Big-O Runtime of a Trie Data Structure?
big-o, data-structures, runtime, trie
Solution
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.
Problem
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?