Question

How many bits are needed to specify the single permutation by min-wise independent family?

(a) O (log n!)

(b) O (n!)

(c) Ω (n^2)

(d) Ω (n)

Asked question is from Hash Tables topic in chapter Hash Tables of Data Structures & Algorithms I

This question was addressed to me in final exam.

Answer 1

The correct choice is (d) Ω (n)

Explanation: The time required for single variant hashing to maintain the minimum hash queue is O (n). Ω (n) bits are needed to specify the single permutation by min-wise independent family.