[Haskell-cafe] Data.IntMap union complexity

Christoph Breitkopf 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.

- chris

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...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120224/41056be2/attachment.htm>

More information about the Haskell-Cafe mailing list