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:54 UTC

On 2021-06-18 15:42 -0400, Wolfgang Corcoran-Mathe wrote:
> 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.

Sorry, I got the math in this example wrong.  An O(min(n, fx-width))
lookup is O(log n) in this case.  Still, I'm not confident that we
could expect O(log n) lookup from all implementations.

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

"A man provided with paper, pencil, and rubber, and subject to strict
discipline, is in effect a universal machine." --Alan Turing