Data Structure for Set Data:a set S of n itemsx,...,=[N] Query:an itemx∈UU Determine whether x E S. Space cost:size of data structure (in bits) entropy of a set:O(n log N)bits (when N>n) Time cost:time to answer a query (in memory accesses) Balanced tree:O(n log N space,O(log n)time Perfect hashing:O(n log N space,O(1)timeData Structure for Set Data: a set of items Query: an item Determine whether . S n x1, x2, …, xn ∈ U = [N] x ∈ U x ∈ S • Space cost: size of data structure (in bits) • entropy of a set: O(n log N) bits (when N≫n) • Time cost: time to answer a query (in memory accesses) • Balanced tree: O(n log N) space, O(log n) time • Perfect hashing: O(n log N) space, O(1) time