Suggestion: Operator `in` for slices

Ola Fosheim Grøstad ola.fosheim.grostad at gmail.com
Sun Dec 19 19:34:18 UTC 2021


On Sunday, 19 December 2021 at 18:36:12 UTC, Steven Schveighoffer 
wrote:
> That is what we claim (and what hash algorithms in general 
> claim). amortized O(1) lookups and inserts.

Yes, if you don't shrink.

You need to prove that the claim holds for all possible orderings 
of inserts, deletions and lookups.

So you need to prove that you always do O(N) operations between 
rehashing, so you get O(N) operations of complexity O(1) + one 
rehash of complexity O(N) = O(N).


More information about the Digitalmars-d mailing list