Re:Hoare’s Rebuttal and Bubble Sort’s Comeback
by kazinator on Sunday May 31, 2020 @10:39AM
(#23369856)
Intersection is calculable in amortized O(M + N) with hashing.
Build hash table in O(N) of the smaller set, then probe M entries of the larger in the table.
If we rely on sorted order, we can make it a requirement/invariant that these sets are maintained in sorted order. Membership in a group rarely changes; if a user is added to a new group, that can be inserted in order. A binary heap structure could be used to keep these objects in array form, while allowing better than linear insertion.
Build hash table in O(N) of the smaller set, then probe M entries of the larger in the table.
If we rely on sorted order, we can make it a requirement/invariant that these sets are maintained in sorted order. Membership in a group rarely changes; if a user is added to a new group, that can be inserted in order. A binary heap structure could be used to keep these objects in array form, while allowing better than linear insertion.