Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value

[Charles Levert]

* On Tuesday 2005-07-05 at 11:12:31 -0700, Paul Eggert wrote:
> Charles Levert <address@hidden> writes:
> 
> > My only fear is that there likely already is a
> > published paper proving just this, probably in
> > a much more elegant way, and that I don't know
> > about it.  Does someone here know?
> 
> I have a copy of Knuth volume 3, and am willing to look it up, but I
> don't know what the algorithm that I'm looking for is.  (I could read
> the grep source code, but I figure it's easier to ask you. :-)

Some key concepts involved:

-- Balanced binary trees (at every node,
   the depth difference of the two subtrees is
   at most 1).

-- Worst (i.e., maximal) depth d_max(n) of such a
   tree as a function of the number n of nodes
   in it.

-- Alternatively, worst (i.e., minimal) number
   n_min(d) of nodes in such a tree of depth d.

      n_min(0) = 0
      n_min(1) = 1
      n_min(d) = d + n_min(0) + ... n_min(n-2)

-- Take n = 2^b; compare floor(1.5 * b)
   and d_max(n) + 1, which is what I did.
   It seems it's an upper bound for b >= 4.
   Adding a term other than 1 doesn't seem to
   produce such a nice property.

-- It just so happens that d_max(n) + 1 is what
   we need (because of an extra first element
   in the array).