[Haskell-cafe] Data.IntMap union complexity
Clark Gaebel
cgaebel at csclub.uwaterloo.ca
Fri Feb 24 03:16:55 CET 2012
Looking at IntMap's left-biased 'union' function [1], I noticed that the
complexity is O(n+m) where n is the size of the left map, and m is the size
of the right map.
Since insertion [2] is O(min(n, W)) [ where W is the number of bits in an
Int ], wouldn't it be more efficient to just fold 'insert' over one of the
lists for a complexity of O(m*min(n, W))? This would degrade into O(m) in
the worst case, as opposed to the current O(n+m).
Or am I just crazy?
Regards,
- clark
[1]
http://hackage.haskell.org/packages/archive/containers/0.4.2.1/doc/html/Data-IntMap.html#v:union
[2]
http://hackage.haskell.org/packages/archive/containers/0.4.2.1/doc/html/Data-IntMap.html#v:insert
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120223/6d9c439a/attachment.htm>
More information about the Haskell-Cafe
mailing list