Consistency
Craig Dillabaugh via Digitalmars-d
digitalmars-d at puremagic.com
Sun Feb 15 20:19:47 PST 2015
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.
More information about the Digitalmars-d
mailing list