Bloom Filters have false positive rate of $\epsilon = 2^{-k}$ with a data structure of size $m = n\log (\frac{1}{\epsilon})\ln 2$. Suppose you fix the number of hash functions at $k \le 3$. What is the correct tradeoff between space ($m$) and false positive rate ($\epsilon$) for $k = 1,2,3$? To get a false positive rate of $1\%$, what size array do you need for $k = 1,2,3$?I'm not sure how to answer the first question (tradeoff between space/false positive rate). For the second question, I'm confused because even if I solve the equation $m = n\log (\frac{1}{\epsilon})\ln 2$ for $\epsilon$, it still doesn't take into consider what $k$ is. For a certain $k$, how do you calculate the false positive probability?
Tradoff between space and false positive rate when using bloom filters
algorithm analysis;data structures;randomized algorithms;sets;hash tables