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
IntMapforMap?Here, in
Mapdocumentation most lookup and insertion operations are indeedO(log n):hackage.haskell.org/package/contai...
But in
IntMapdocumentation, 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
IntMapcontains more than 64 elements, the time complexity is constantO(W)orO(1).Interesting .. I wasn't aware of that.