[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: |
Paul Eggert |
Subject: |
Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value |
Date: |
Thu, 07 Jul 2005 16:48:49 -0700 |
User-agent: |
Gnus/5.1007 (Gnus v5.10.7) Emacs/21.4 (gnu/linux) |
Charles Levert <address@hidden> writes:
>> The height of a balanced binary tree with N internal nodes always lies
>> between lg(N + 1) and (1.4404 lg (N + 2) - 0.3277). Here, the
>> "internal nodes" are those with children,
>
> Unfortunately, in this case I use n for all
> nodes, internal and leaves.
If you have N internal nodes, then you have N + 1 leaf nodes, for a
total of 2*N + 1 nodes, so it shouldn't be hard to substitute your
variables for Knuth's. But I would stick with Knuth's notation
myself; why reinvent the wheel?
> This is ok, though. The floor(1.5 * b) formula
> is still the best and simplest one we can use,
I disagree! You don't have a proof. Knuth does. You should be able
to derive your lower bound from Knuth's; if you can't, then there's
something really fishy going on.
- 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, 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, 2005/07/07
- Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value,
Paul Eggert <=
- 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