Recursively rotated orders and implicit data structures: A lower bound (Q792764)

Let n values be stored in the first n locations of an array. Suppose that a dictionary is maintained on these values, so that the operations of insert, delete, and search are supported. Since no additional space is allowed, no explicit pointers can be used. Thus any information about the relationship of values must be encoded in their arrangement. Such a structure is called an implicit data structure. The paper addresses a relaxation of a sorted order, called a recursively rotated order. If the values are stored in a fashion consistent with such an order, search times of \(O(\log n)\) can be achieved. The main result of the paper is that the number of data swaps for an exchange (an insertion of one element combined with a deletion of another element) for any such order is in the worst case \(\Omega(2^{\sqrt{2 \log n}}(\log n)^{1/2}).\) This matches to within a constant factor an upper bound on the number of data swaps.