[Haskell-cafe] Data.IntMap union complexity

[Serguey Zefirov]

2012/2/24 Clark Gaebel <cgaebel at csclub.uwaterloo.ca>:
> 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?

This way you will create much more garbage, I think. The union of two
completely disjoint maps can hold parts of them intact.