Model

Elias–Fano: space of a sorted sequence

Within about half a bit per element of the information-theoretic bound for monotone sequences, with random access.

bits = n (2 + ⌈ lo g_{2} \frac{u}{n} ⌉)

How it behaves

One input on the horizontal axis, the others held fixed.

Data table

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

Core Data Structures
How do we choose a data structure when the real cost is set by the hardware, not by Big-O?
$n \cdot (2 + ⌈ lo g_{2} (u / n)⌉) bits$
Read it in place →