Re: A very basic thing I don't get

[David Kastrup <dak@...>]

Pierpaolo Bernardi <olopierpa@gmail.com> writes:

> On Mon, Oct 3, 2011 at 12:30, Axel Kittenberger <axkibe@gmail.com> wrote:
>> Just because not every slot is filled doesn't yet mean that O() isn't 1.Eg a
>> btree will never go below ~50% load.
>
> So btrees are O(1). Other structures are not.
>
> Trees where information is kept only at the terminal leaves are a fairly
> common components of many data structures. These are not O(1).

If they have a minimum fanout f>1 (like trees where nodes with one or no
child are collapsed), they are.  It is often possible to make it so, but
by no means mandatory.

-- 
David Kastrup