Tight(er) worst-case bounds on dynamic searching and priority queues
Arne A. Andersson, Mikkel Thorup · 2000
We introduce a novel technique for converting static polynomial space search structures for ordered sets into fully-dynamic linear space data structures. Based on this we present optimal bounds for ...