Sets as Sorted Arrays
Costs for set operations on sorted array:
- card: read from struct; O(1)
- member: binary search; O(log n)
- insert: find, shift up, insert; O(n)
- delete: find, shift down; O(n)
- union: merge = scan s1, scan s2; O(n) (technically O(n+m))
- intersect: merge = scan s1, scan s2; O(n) (technically O(n+m))
|