Re: A very basic thing I don't get

[Leo Razoumov <slonik.az@...>]

On Mon, Oct 3, 2011 at 06:40, David Kastrup <dak@gnu.org> wrote:
> Axel Kittenberger <axkibe@gmail.com> writes:
>
>> 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.
>
> Radix trees fan out according to the size of the data, not just its
> amount.  Unbalanced trees can have less that 50% load.
>
> --
> David Kastrup
>

Also, a balanced trie (prefix tree) with N values stored in leaves has
O(N*log(N)) nodes making it  O(log(N)) per value in size.
For a non-balanced trie it could be even worse.

--Leo--