On Sunday, 15 February 2015 at 18:45:45 UTC, bearophile wrote:
Meta:
Oh, whoops. I mixed up average-case complexity with
worst-case. Although, isn't lookup O(n) in the worst case for
hash tables?
D associative arrays used to be O(1) amortized and O(n ln n) in
worst case. Now they are O(1) amortized and O(n) worst case.
And for an adversary it's not too much hard to find and hit
that O(n) case.
Bye,
bearophile
How is it possible to have a search structure that takes O(n ln n)
time ... you would have to go out of your way to design something
particularly bad.
