# An algorithm for finding predecessors in integer sets

Published

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