Are new sequences really O(1)?

[Einar Karttunen]

Adrian Hey <ahey at iee.org> writes:
> This is quite impressive. For moderate length sequences, it seems
> to be about twice as fast as AVL (which AFAIK is the fastest
> balanced tree implementation currently available for Haskell).
> The execution times are growing slower than AVL for longer
> sequences too (looks more like O(1) than it did before, but
> still not quite O(1) for some reason).

Garbage collection is not O(1) and data moves out of cache, 
so there will be no true O(1), just something which looks 
like it would be O(1) in a perfect world.

- Einar Karttunen