DEV Community

loading...

Discussion on: Daily Challenge #273 - Remove Duplicates

Collapse
akashkava profile image
Akash Kava

You are forgetting OLog(n) steps used by IntMap internally, it is never O(n),

Thread Thread
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.