Sets and multisets

A set: hash table of keys — O(1) membership, no duplicates. A multiset: keys with counts.

Two questions, answered in O(1)

• Set — "have I seen this?" (membership, dedup)
• Multiset — "how many of each?" (counting)
• Plus an algebra: union, intersection, difference
• All built on O(1) membership

Watch an intersection

Probe each element of A for membership in B. 1,2,3 miss; 4,5,6 hit → A ∩ B = {4,5,6}. Each probe O(1).

Complexity

• add / contains / remove: O(1) average
• union: O(n+m) · intersection: O(smaller) · difference: O(n)
• x in list is O(n); x in set is O(1)

The seen-set pattern

Record what you've seen → turn O(n²) scans into O(n). The most useful trick in the book.

Takeaway

Membership in O(1) → dedup, "seen before", counting. No order, no duplicates. Next tier: recursion & sorting.