<font face="verdana,sans-serif">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.<br><br>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).<br>
<br>Or am I just crazy?<br><br>Regards,<br> - clark<br><br>[1] <a href="http://hackage.haskell.org/packages/archive/containers/0.4.2.1/doc/html/Data-IntMap.html#v:union">http://hackage.haskell.org/packages/archive/containers/0.4.2.1/doc/html/Data-IntMap.html#v:union</a><br>
[2] <a href="http://hackage.haskell.org/packages/archive/containers/0.4.2.1/doc/html/Data-IntMap.html#v:insert">http://hackage.haskell.org/packages/archive/containers/0.4.2.1/doc/html/Data-IntMap.html#v:insert</a><br></font>