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