There is a quite a bit of information about the time complexity of inserting words into a Trie data structure, but not a whole lot about the space complexity.I believe the space complexity is O(n**m), where:n: possible character countm: average word lengthFor example, if the available characters are a and b, then n is 2, and the average length of the words, m is 5, wouldn't the worse case be the space usage of 32 (2**5)?This is my visualisation of this example:
What is the space complexity for inserting a list of words into a Trie data structure?
algorithms;data structures
Let w be the amount of words in the trie. Then the boundary O(w*m) is much more useful, since it simply represents the max amount of characters in the trie, which is obviously also it's space boundary.In a way, yes, O(n**m) is a correct boundary too. It's just pretty useless in most cases. For example, w = 200 words with an average length of m = 100 in an alphabet size of n = 50 would result in O(50**100), woot, doesn't fit in the universe! ...while the other boundery would be O(200*100).