[Haskell-cafe] Data.IntMap union complexity

[wren ng thornton]

On 2/23/12 10:22 PM, Clark Gaebel wrote:
> The situation I encounted this is doing a batch update of a map. Is there
> an easy way to do that? I'm doing something like adding 20-or-so elements
> to an existing map of a few thousand.

The O(m+n) of the merging functions is actually on the order of the size 
of the spine intersection between the two maps. Thus, it only ever 
approaches that limit in cases where the maps are of approximately equal 
size and are designed for the spines to clash in the worst way. An 
example would be if you're merging the set of all even numbers and the 
set of all odd numbers; you have to traverse the whole tree up to the 
last bit. Ditto for taking the union of a set with itself.

When the two maps are of vastly different sizes, O(min(m,n)) is a more 
intuitive way to think about it. Since you only have to look at the 
places where the spines clash, that will be on the order of the smaller map.

-- 
Live well,
~wren