19.12 Complexity

The elementary transformations are simultaneous left-to-right scans. Each step either advances a list or splits an interval at a newly encountered boundary, so a scan is linear in the intervals it visits plus the intervals it creates.

Given pointers to the affected nodes, inserting, removing or coalescing an ordinary interval changes a fixed number of doubly linked-list pointers and is (O(1)). A move performs this independently in its insertion and extraction lists. Splitting or relocating an alias group is linear in the number of aliases in that group. Locating the destination of a relocated group is linear in the portion of the destination list scanned.

Ordering competing moves by e is important. Two groups of (m) and (n) aliases are transformed or merged in (O(m+n)), rather than comparing all (mn) pairs.