2 ms·
Really? Looks to me like the lookup function is invoking recursion here: https://en.wikipedia.org/wiki/Trie#Algorithms https://en.wikipedia.org/wiki/Trie#Algori
by marshray 14y ago
Really? Looks to me like the lookup function is invoking recursion here:
https://en.wikipedia.org/wiki/Trie#Algorithms https://en.wikipedia.org/wiki/Trie#Algorithms
I would think the amortized cost would be O(log_b n), with b being something like the Shannon entropy of each symbol.
- aidenn0 14y agoWell in that case the cost of a hash-function is also not O(1) since the minimum length of a n distinct keys is log(n). Really both a trie and a hash-function boil down to O(m) where m is the length of the key.