Re: A very basic thing I don't get

[Pierpaolo Bernardi <olopierpa@...>]

On Mon, Oct 3, 2011 at 12:02, Axel Kittenberger <axkibe@gmail.com> wrote:
>> So, say, you never heard of trees, which btw are ridiculous data
>> structures.  8^)
>
> They have O(1) per item for space, a tree which load would reduce even by
> O(log(n)) would be ridiculous.

You are right that some tree representation are O(1) per item.
Others, perfectly sensible representations, are not.

E.g. representations in which not every node contains an item,
an example of which is the representation of sexpr as usually
implemented in lisp-like languages.

Other examples are common in functional programming, where
the overhead in space is compensated by other nice properties.

P.