is there a set implementation with less than O(n) space

Question

Suppose I want to implement a Set structure. support
1 .add operation to add an element into the set
2. exist operation to check an element is in the set.
(no data lose is allowed and no assumption about the data. You can think them as random generated number with a very lang range)

I know some implementation can achive O(1) time complexity and O(n) space complexity. If I can tolerate higher time complexity, is there a implementation with less than O(n) space complexity?

Answer 1

The requirement of less than O(n) space looks nonsensical — you have to store information on all the stuff you have inserted to support your queries.

What you can actually implement depends on which requirements you can sacrifice.

A previous version of this answer contained the idea of using Bloom filter, but its space complexity is also O(n), so no, this is not a useful solution.