Are new sequences really O(1)?

Einar Karttunen ekarttun at
Fri May 27 11:20:06 EDT 2005

Adrian Hey <ahey at> 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

More information about the Libraries mailing list