0
$\begingroup$

Succinct data structure = succinct representation of data + bits for indexing. Link

Let $S$ be subset of of $\{1,2,\ldots,n\}$ then $\lceil \log (2^n) \rceil + o(\log n )$ bits are needed in succinct representation. The $o(\log n)$ bits needed for the indexing of the succinct data structure. I have a doubt, why $o(\log n)$ not $O(\log n)$ bits? Where $O(\log n)$ do not play any role when talking about conventional representation of data.

$\endgroup$
2
$\begingroup$

Note that $\lceil \log(2^n) \rceil = n$.

An algorithm that uses $n$ bits to represent the set would be fine (it would count as a succinct data structure). An algorithm that uses $n + 2 \sqrt{n}$ bits would also be fine.

An algorithm that uses $2n$ bits to represent the set would not be fine (it would not count as a succinct data structure). Similarly, an algorithm that uses $1.01n$ bits would not be fine.

This is just what the definition says. You could imagine some other definition, but that's what the standard definition of "succinct data structure" is saying. It is saying that you can use a little bit more space than required by the information-theoretic lower bound, but not too much -- not a multiplicative factor.

$\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.