[Haskell-cafe] Data.IntMap union complexity
chbreitkopf at googlemail.com
Fri Feb 24 09:40:08 CET 2012
Folding insert might still be a win if one of the maps is very much smaller
than the other, but since size is O(n) for Data.IntMap, there's no way to
find out if that's the case.
On Fri, Feb 24, 2012 at 4:48 AM, wren ng thornton <wren at freegeek.org> wrote:
> 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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe