4 ms·
> HAMTs are hash tries. O(log(n)) lookup, but persistent / cheep to copy. O(LOG(k)) might be a clearer bound rather than n.
by naasking 3y ago
> HAMTs are hash tries. O(log(n)) lookup, but persistent / cheep to copy.
O(LOG(k)) might be a clearer bound rather than n.
- cbarrick 3y agoFor a hash trie, the depth is bounded by the log of the number of elements: O(log(n)). I think O(log(k)) would mean that the bound is based on the size of the largest key. This may be true of regular tries, but not of hash tries.