Online List Labeling: Breaking the log^2 n Barrier
summary
Provides a randomized data structure that stores n items in m = Θ(n) array slots and achieves expected O(log^{3/2} n) item moves per insertion/deletion, improving the long-standing O(log^2 n) upper bound. Construction layers nested intervals, uses lazy rebalancing plus a random shift, detects a 1/polylog fraction of dense regions and falls back to the classic log^2 n rebalance there. Key tools are a random-walk density analysis and enforced history independence to hide dense spots from an oblivious adversary; the scheme matches a history-independent lower bound.
AI-written summary · about