Hi and thanks for your reply. This looks like a very good solution.

Wouldn't this have O(n^2) time complexity?

Indeed this algorithm would have an O(n²) time complexity if the xs list would remain the same. I believe the time complexity is O(n log n) since we are decreasing the xs list each time in the solution I proposed. But I'm bad at time complexity so I wouldn't know.

I didn't know about Data.IntSet I'll look into that. Thanks for sharing.

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

HaskellTest

Wouldn't this have

`O(n^2)`

time complexity? This could be done in`O(n)`

, using a`IntMap`

.EDIT:This is my attempt at writing a similar function but with

`O(n)`

time complexity (`O(n*m)`

when`m <= 64`

, where`m`

is amount of elements in`IntSet`

):Hi and thanks for your reply. This looks like a very good solution.

Indeed this algorithm would have an

`O(n²)`

time complexity if the`xs`

list would remain the same. I believe the time complexity is`O(n log n)`

since we are decreasing the`xs`

list each time in the solution I proposed. But I'm bad at time complexity so I wouldn't know.I didn't know about

`Data.IntSet`

I'll look into that. Thanks for sharing.You are forgetting OLog(n) steps used by IntMap internally, it is never O(n),

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)`

.Interesting .. I wasn't aware of that.