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