Variable chunk sizes operations

[Paul Backus]

On Saturday, 29 August 2020 at 23:33:49 UTC, Mihaela Chirea wrote:
> I started working on this issue and I reached a point where 
> some more opinions would be needed:
>
> https://github.com/dlang/phobos/pull/7600
>
> Since the range is split into uneven parts, some operations can 
> only be done in O(n).

I think care should be taken to distinguish which `n` we're 
talking about when we use terms like O(n) in this context.

For example, let's say N = the length of the source range, and S 
= the length of the chunk-sizes range. Your length method is 
O(S), but not O(N)--in fact, it runs in constant time w.r.t. the 
length of the source range.

I'm not sure what Phobos policy is regarding time complexity for 
algorithms that take multiple ranges (does it have to be O(1) 
w.r.t. *all* arguments?), but given that S is likely to be 
smaller than N, there's a case to be made that the linear-time 
algorithm is reasonable here.

(A similar case is binary search of a range that contains strings 
runs in logarithmic time w.r.t. the length of the range, but 
linear time w.r.t. the length of the target string, because 
checking two strings for equality is a linear-time operation.)