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).
Wouldn't this have
O(n^2)
time complexity? This could be done inO(n)
, using aIntMap
.EDIT:
This is my attempt at writing a similar function but with
O(n)
time complexity (O(n*m)
whenm <= 64
, wherem
is amount of elements inIntSet
):Hi and thanks for your reply. This looks like a very good solution.
Indeed this algorithm would have an
O(n²)
time complexity if thexs
list would remain the same. I believe the time complexity isO(n log n)
since we are decreasing thexs
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
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.