An algorithm for finding predecessors in integer sets


Conference Paper

© Springer-Verlag Berlin Heidelberg 1993. This paper presents a data structure that supports the operations of inserting and deleting elements drawn from a universe U={0⋯u-1} into a set S, and for finding the predecessors of elements of U in S. We consider both random inputs and worst-case inputs. In the case of random inputs, we show that each operation can be performed in constant time, with high probability, provided that the total number of operations is at most polynomial in u. In Yao’s cell probe model, the algorithm uses O(n) space, where n is the maximum size that S achieves during the sequence of operations. The algorithm can be implemented with the same performance in the RAM model with word size O(log u) at the cost of performing uϵpreprocessing operations, and using u? additional space, for any fixed ϵ > 0. The algorithm can be modified so that even in the worst case no operation takes more than O(log log u) time, at the cost of using O(u) additional space.

Duke Authors

Cited Authors

  • Maggs, B; Rauch, M

Published Date

  • January 1, 1993

Published In

Volume / Issue

  • 709 LNCS /

Start / End Page

  • 483 - 493

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783540571551

Citation Source

  • Scopus