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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
