6.042J Lecture Notes - Lecture 20: Pigeonhole Principle, Bijection, Disjoint Sets
13 Apr 2016
School
Course
Professor
Document Summary
Number of operations to update a data structure. This is the same as saying how many comparisons are needed to sort n items. This is the same as saying how many multiplications are needed to compute d. Sum rule: if sets a and b are disjoint, then the number of elements in their union is simply the sum of the number of elements in the two sets. Example: if a class has 43 women and 54 men, then the total enrollment is 97 students. Example: there are 26 lower case letters, 26 upper case letters, and 10 digits, so there are 62 characters. Product rule: if there are sets a and b such that |a| = m and |b| = n, then |a x b| = mn. Note: a x b denotes all possible ordered pairs such that the rst element is from a and the second element is from b.
