Guarantee some algorithmic complexities? Marc Nieper-Wi├čkirchen (16 Jun 2021 09:50 UTC)
Re: Guarantee some algorithmic complexities? Ray Dillinger (16 Jun 2021 15:56 UTC)
Re: Guarantee some algorithmic complexities? Wolfgang Corcoran-Mathe (16 Jun 2021 17:41 UTC)
Re: Guarantee some algorithmic complexities? Marc Nieper-Wi├čkirchen (16 Jun 2021 18:16 UTC)
Re: Guarantee some algorithmic complexities? Wolfgang Corcoran-Mathe (18 Jun 2021 19:42 UTC)
Re: Guarantee some algorithmic complexities? Wolfgang Corcoran-Mathe (18 Jun 2021 19:54 UTC)

Re: Guarantee some algorithmic complexities? Wolfgang Corcoran-Mathe 18 Jun 2021 19:42 UTC

On 2021-06-16 20:16 +0200, Marc Nieper-Wißkirchen wrote:
> That said, is there any conceivable case where it makes sense to implement
> fxmappings where, say, lookup takes O(n)?

Not in my opinion, but I don't consider such a bound useful.  If we
were to provide low-ball bounds which only very inefficient
implementations violate, it wouldn't give users of SRFI 224 any idea
of what they can expect from more efficient implementations.

It's also not clear to me what those low-ball bounds are.  For the
sample implementation's radix trees, lookup is O(min(n, fx-width)) in
time for a tree of n elements; in practice, it's log n time except in
unusual cases.  Be that as it may, requiring O(log n) time, for
instance, would make this an unacceptable implementation.

Coming up with acceptable general bounds for fxmapping operations is
beyond my current knowledge, and I'd want to do a decent amount of
research before adding anything of this sort to the SRFI.

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

"Nothing can transcend its smallest elements." --CEO Nwabudike Morgan