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