A linear lower bound for incrementing a space-optimal integer representation in the bit-probe model

M. Raskin

We present the first linear lower bound for the number of bits required to be accessed in the worst case to increment an integer in an arbitrary space- optimal binary representatio…