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:
Best Answer
Let
w
be the amount of words in the trie. Then the boundaryO(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 ofm = 100
in an alphabet size ofn = 50
would result inO(50**100)
, woot, doesn't fit in the universe! ...while the other boundery would beO(200*100)
.