lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On Mon, Oct 3, 2011 at 06:40, David Kastrup <> wrote:
> Axel Kittenberger <> 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.