Recursively rotated orders and implicit data structures: A lower bound

AbstractA lower bound is derived for the time required to perform an update in an implicit data structure that is stored in a recursively rotated order. The update is shown to require Ω(22logn (log n) 12) data swaps, where n is the number of elements in the structure. This matches an upper bound derived in an earlier paper (Frederickson, 1983)