bug-grep
[Top][All Lists]

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

 From: Charles Levert Subject: Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value Date: Tue, 5 Jul 2005 15:42:50 -0400 User-agent: Mutt/1.4.1i

```* On Tuesday 2005-07-05 at 11:12:31 -0700, Paul Eggert wrote:
>
> > 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).

```