# What is the space complexity for inserting a list of words into a Trie data structure?

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 count`

`m`: `average word length`

For 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: • Data structures do not have time complexity. Algorithms working on data structures have time complexity. – Timothy Truckle May 5 '17 at 20:09
• A quick Google Search verifies that the space complexity of a trie is `O(ALPHABET_SIZE * key_length * N)`. See geeksforgeeks.org/trie-insert-and-search – Robert Harvey May 5 '17 at 22:49
• I noticed you put a bounty on this question and selected the reason "a detailed canonical answer is required to address all the concerns." Can you be specific about what concerns you would like us to address? – Robert Harvey May 18 '17 at 14:06

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)`.
Another way of thinking this is space being `O(kN)`, where `k` is the count of possible characters (assuming we are using array to store the mapping), `N` is the number of nodes in trie.
Whereas more meaningfully, from the client's perspective, the space complexity is `O(mn)`, where `m` is the average length of strings inserted, `n` is the number of words. This calculation assumes hashmap mapping, and `O(mn)` gives an upperbound because it does not consider common prefix.