[Haskell-cafe] Data.IntMap union complexity
Kazu Yamamoto ( 山本和彦 )
kazu at iij.ad.jp
Fri Feb 24 03:38:36 CET 2012
Hello,
> 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).
Interesting.
I would point out that the original paper "Fast Mergeable Integer
Maps" says that merge is O(n+m).
I don't know which one is correct.
--Kazu
More information about the Haskell-Cafe
mailing list