Tight Lower Bound for on-Line Monotonic List Labeling

摘要

Maintaining a monotonic labeling of an ordered list during the insertion of nitems requires Omega(n log(n)) individual relabelings, in the worst case, if the number of usable labels is only polynomial in n.