Review time complexities of `difference[With[Key]]`

[sjakobi]

See #542 (comment).

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.