Are new sequences really O(1)?
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