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