[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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:
> 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).
- src/kwset.c (kwsincr): Replace arbitrary array size by proper value, Charles Levert, 2005/07/04
- Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value, Julian Foad, 2005/07/04
- Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value, Paul Eggert, 2005/07/05
- Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value, Charles Levert, 2005/07/05
- Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value, Paul Eggert, 2005/07/05
- Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value,
Charles Levert <=
- Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value, Paul Eggert, 2005/07/05
- Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value, Charles Levert, 2005/07/07
- Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value, Paul Eggert, 2005/07/07
- Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value, Charles Levert, 2005/07/08
- Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value, Charles Levert, 2005/07/08
- Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value, Paul Eggert, 2005/07/08