Suggestion: Operator `in` for slices
Ola Fosheim Grøstad
ola.fosheim.grostad at gmail.com
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