Re: 5.2 work3 manual

["Juris Kalnins" <juris@...>]

On Tue, 25 May 2010 16:23:20 +0300, Tony Finch <dot@dotat.at> wrote:

> On Tue, 25 May 2010, Juris Kalnins wrote:
> > When resizing array part, link all nil nodes into firstNil list;
> > then #t is:
> > *firstNil ? #t == array - firstNil : sizearray;
> >
> > And you have O(1) #t, plus amortized O(1) cost of list upkeep.
>
> Not if you need to insert a nil in the middle of the list.

Hmm, right, but it still doesn't affect the cost of #t ;)

And non-pathological inserting of nil is not O(n), either.
(If there are "few" holes, you can find nil, closest to
the position of the new nil "fast" by traversing the list.
If there are "many", by randomly probing the nodes in the
yet-not-traveled range. Search that does this in parallel
_i_think_ is faster than O(n)).