Implicit dictionaries supporting searches and amortized updates in O(log n log log n) time
Gianni Franceschini, Roberto Grossi · CINECA IRIS Institutial research information system (University of Pisa) · 2003
We describe a new implicit data structure for maintaining n data values in the first n locations of an array. No information other than n and the data is to be retained, and the only operations which we may perform on the data values (other than reads and writes) are comparisons. Our structure supports searches in O(log n log log n) time in the worst case, and insertions and deletions in O(log n log log n) amortized time. The best known bound for these operations in main memory is O(log 2n/log log n) in the worst case.