0
$\begingroup$

Let $S= \{1,2,3...,n\}$ be a set and I want to store a subset of $A \subseteq S$. Is there exists any data structure such that insert$(x)$, delete ($x$) can be done in amortised $O(1)$ time and search($x$) can be done in $O(1)$ time, where $x\in A$. Space used by data structure should be $O(n \log^{*}n)$ or $O(n)$ bits. Model of computation is RAM.

$\endgroup$
1
$\begingroup$

Bit vectors fulfill all your requirements.

$\endgroup$
0
$\begingroup$

Bit vectors, as mentioned by Raphael, fulfill all the requirements and it is a very simple and fast option. But there is an alternative called Minimal Perfect Hashing, which could be represented succinctly requiring few bits in practice.

A bit vector $B$ can also be compressed in order to achieve $$O(nH_0(B)) \text{ bits}$$ of space. Depending on the distribution of 0's and 1's, this could be $o(n)$ bits.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.