Are new sequences really O(1)?

Einar Karttunen ekarttun at cs.helsinki.fi
Fri May 27 11:20:06 EDT 2005


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


More information about the Libraries mailing list