[prev] 32 [next]

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))