On 2020-09-07 11:44 -0400, Wolfgang Corcoran-Mathe wrote:
> On 2020-09-07 08:31 +0200, Marc Nieper-Wißkirchen wrote:
> > >> So, actually, procedures like range-every (that have to
> > >> inspect all ranges at least once) also need addition of O(k).
> > >
> > >
> > > But that's done in the proc argument, and running time there is not
> > > counted.  I've made the change, but it's easy to roll back if I'm correct.
> >
> > All the zillion ranges passed to range-every can be empty so proc is
> > never called. But range-length will have to be called on them. That's
> > why it needs at least O(k) time.
>
> Indeed.  A zillion empty ranges is a fast case for range-every, but
> we must still determine that they are all empty.

(Again, a slight oversimplification.  We need only determine that one
of the zillion ranges is empty to short-circuit.  In the worst case,
we still need to check all k ranges.)

--
Wolfgang Corcoran-Mathe  <xxxxxx@sigwinch.xyz>