Suggestion: Operator `in` for slices

Ola Fosheim Grøstad ola.fosheim.grostad at
Sun Dec 19 11:45:58 UTC 2021

On Sunday, 19 December 2021 at 11:07:30 UTC, Ola Fosheim Grøstad 
> Average case is not given with Big-Oh-notation, but done 
> "accurately" by presenting a model for the distribution of 
> input data and then solving it. (usually a very big task)

By this I mean that using "O(…)" alone means worst case.

We can say that quicksort is O(N²). Not qualifying the statements 
implies worst case.

If we consider all inputs equally likely then we can also claim 
that the average case complexity is limited by O(N log N).

Now, if AA was implemented as a hashtable with a constant 
upper-bound on the linked lists (say 100) then we could say that 
"in" would be O(1).

We could also claim that inserts would be O(1) amortized (ignore 
rehashing, assuming a distribution that is relatively flat).

So in general, we should be able to have AAs where all operations 
(insert, delete and membership tests) are O(1) amortized.

More information about the Digitalmars-d mailing list