Suggestion: Operator `in` for slices

[Ola Fosheim Grøstad]

On Sunday, 19 December 2021 at 10:10:21 UTC, Dukc wrote:
> function sees "Ah, an `in` operator. `in` is on average O(log 
> N) at worst, I can call it hundreds of times without 
> significant slowdown", and compiles such that it takes a 
> quarter of an hour to execute.

I know this is a common abuse of notation in C++ circles, but 
O(…) means worst case.

Also if something is O(log N), then it is also O(N) or any other 
bigger bound. The notations O(N) means that N is sufficient to 
put an upper bound on the computation growth (in terms of input 
size) for each and every possible input of any size.

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)

When some C++ libraries talk of amortized complexity, they 
probably should not use O-notation, but we get what they mean. 
E.g. if you do a long series of operations then the costly 
reallocations will be amortized, so they therefore ignore it in 
the analysis and "pretend" it does not happen.

But it isn't on average. To do on-average-calculations you need a 
model of the input and the operations, and the calculcations can 
take a scholar many days to figure out. E.g. one strategy is to 
translate the model and patterns of operations to recurrence 
relations and solving it as integrals… a very tedious and time 
consuming job.