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).
You are forgetting OLog(n) steps used by IntMap internally, it is never O(n),
Perhaps you're mistaking
IntMap
forMap
?Here, in
Map
documentation most lookup and insertion operations are indeedO(log n)
:hackage.haskell.org/package/contai...
But in
IntMap
documentation, you can see that the actual complexity isO(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 constantO(W)
orO(1)
.Interesting .. I wasn't aware of that.