* On Tuesday 2005-07-05 at 11:12:31 -0700, Paul Eggert wrote:
> Charles Levert <[EMAIL PROTECTED]> 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).
