Re: Are new sequences really O(1)?

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