Question

What is the time required for single variant hashing to maintain the minimum hash queue?

(a) O (log n!)

(b) O (n!)

(c) O (n^2)

(d) O (n)

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

I have been asked this question during an online exam.

Answer 1

Right choice is (d) O (n)

The explanation is: The expected error for estimating the Jaccard index using MinHash scheme for k different hash functions is O (1/k½). The time required for single variant hashing to maintain the minimum hash queue is O (n).