DEV Community

loading...

Discussion on: Daily Challenge #273 - Remove Duplicates

cipharius profile image
Valts Liepiņš

Perhaps you're mistaking IntMap for Map?

Here, in Map documentation most lookup and insertion operations are indeed O(log n):
hackage.haskell.org/package/contai...

But in IntMap documentation, you can see that the actual complexity is O(min(n, W)), where W is size of integer type (32 or 64):
hackage.haskell.org/package/contai...

This effectively means that after IntMap contains more than 64 elements, the time complexity is constant O(W) or O(1).

Thread Thread
akashkava profile image
Akash Kava

Interesting .. I wasn't aware of that.