3 ms·
I would hope not to use any additional space. A naive approach is to choose 1 bit out of N from the first hash, 1 out of the remaining N-1 from the second hash,
by anonymoushn 6y ago
I would hope not to use any additional space. A naive approach is to choose 1 bit out of N from the first hash, 1 out of the remaining N-1 from the second hash, and 1 out of the remaining N-2 from the third, and so on.
- gopiandcode 6y agoThat would fix the final independence problem, but it would also require further changes to other stages of the proof. For example, this strategy would then mean that when calculating the probability of a single bit being set, the hash outcomes are no longer independent, which means that a different expression would be needed. Additionally, from a practical sense, this variation might also be more costly to execute, as setting bits would go from a single memory access to a linear scan. I think it might be interesting to look into though.
- anonymoushn 6y agoYou can decide which bits to set for an input in k^2 time I guess, not k*n time, then set each one with a single memory access.