snippetMinor
How to store $n$ numbers with space $O(n)$ bits and access time $O(1)$?
Viewed 0 times
spacewithbitsnumbersstoretimehowandaccess
Problem
I want to store a subset of $\{1,2,\dots,n\}$ in a data structure such that the total space used is $O(n)$ bits and accessing a particular element can be done in $O(1)$ time. I have tried binary search tree and array data structures but they are too slow.
In short I need a data structure with $O\big(\frac {n } { \log \log n}\big)$ many cells and size of each cell should be $O(\log \log n)$ bits.
Model of computation: Input memory and a write only output memory. The computation proper takes place in a working memory of limited size. When stating a problem can be solved with in a certain bits, what we mean is that the working memory comprises that many bits. The input and working memories are divided into words of $w$ bits for a fixed parameter $w$, arithmetic and logical operations on $w$-bit words take constant time, and random access to the input and working memories is provided. In the context of inputs of $n$ words,$w= \theta(\log n)$.
Operations: Insert($i$), access($i$), where $i \in [n]$. The access operation must run in $O(1)$ time.
Motivation: I'd like to store the stack in DFS using this data structure.
I am looking for an deterministic approach, but to me it does not seems working, so probabilistic approach is also fine.
In short I need a data structure with $O\big(\frac {n } { \log \log n}\big)$ many cells and size of each cell should be $O(\log \log n)$ bits.
Model of computation: Input memory and a write only output memory. The computation proper takes place in a working memory of limited size. When stating a problem can be solved with in a certain bits, what we mean is that the working memory comprises that many bits. The input and working memories are divided into words of $w$ bits for a fixed parameter $w$, arithmetic and logical operations on $w$-bit words take constant time, and random access to the input and working memories is provided. In the context of inputs of $n$ words,$w= \theta(\log n)$.
Operations: Insert($i$), access($i$), where $i \in [n]$. The access operation must run in $O(1)$ time.
Motivation: I'd like to store the stack in DFS using this data structure.
I am looking for an deterministic approach, but to me it does not seems working, so probabilistic approach is also fine.
Solution
A simple solution is to use a $n$-bit bitvector. This is basically an array with $n$ entries, where each entry is either 0 or 1. If the $i$th entry is 1, that means that $i$ was stored in the data structure; 0 means that $i$ was not stored in the data structure. This takes $O(n)$ bits of space. The insert and access operations can be done in $O(1)$ time.
The crucial requirement that makes this solution possible is that there will be no duplicates; each number is present at most once. If you allowed duplicates, the problem would not be solvable within the space requirements you list: storing $n$ numbers from $1$ to $n$ requires at least $\Theta(n \log n)$ bits, based on information-theoretic concerns.
The crucial requirement that makes this solution possible is that there will be no duplicates; each number is present at most once. If you allowed duplicates, the problem would not be solvable within the space requirements you list: storing $n$ numbers from $1$ to $n$ requires at least $\Theta(n \log n)$ bits, based on information-theoretic concerns.
Context
StackExchange Computer Science Q#80912, answer score: 3
Revisions (0)
No revisions yet.