Timeline for How to store $n$ numbers with space $O(n)$ bits and access time $O(1)$?
Current License: CC BY-SA 3.0
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 10, 2017 at 6:55 | comment | added | rici | If order is unimportant, you can store $n$ not necessarily unique numbers from $1$ to $n$ using $2n$ bits: Let $c_i$ be the number of occurrences of $i$. The code is the concatenation of $0^{c_i}1$ for each $i$ from $1$ to $n$. That clearly has $n$ zeros and $n$ ones. The information theoretic limit is smaller than $2n$, since most $2n$-bit numbers don't have the same number of zeros and ones. (Of course, this encoding doesn't give you $O(1)$ access.) | |
| Sep 8, 2017 at 20:22 | history | answered | D.W.♦ | CC BY-SA 3.0 |