See https://github.com/haskell-unordered-containers/unordered-containers/pull/542#discussion_r2496304340. We currently claim `O(n log m)`, but that seems rather high. For comparison, `Data.Map.difference` is `O(m log(n/m + 1)), 0<m≤n`, based on this paper: https://arxiv.org/abs/1602.02120v4.
See #542 (comment).
We currently claim
O(n log m), but that seems rather high.For comparison,
Data.Map.differenceisO(m log(n/m + 1)), 0<m≤n, based on this paper: https://arxiv.org/abs/1602.02120v4.