Assume a bloom filter api, with 2 parameters - 1. number of bits in bloom filter (n) and 2. expected number of insertions (m).
Will m > n always lead to complete false positives? By complete I intend to say, will every test for 'contains(element)' method return true, after m > n condition ?
The bloom filter will always answer yes not when your m > n, but when all n of its bits are 1 - then every query of h positions (where h is the number of hash functions) will yield h 1s. Still, the typical setup that optimizes the space vs. false positive rate tradeoff is when the probability of any bit being set is 1/2. The analysis is shown on the Bloom filter wikipedia article: http://en.wikipedia.org/wiki/Bloom_filter
