The predecessor query in step 1 takes constant time. The operations in step 2 and step 4 are all standard RAM or UWRAM operations, except for finding the leftmost 1-bit which takes constant time [1]}. The dictionary updates in step 3 run in amortized expected constant time by Theorem REF . Since the rest of step 3 also consists of standard operations, the running time for insertions is amortized expected constant.
