[shrughes]

Being better than O(n) worst case is the target here, not O(1) amortized. For example, O(1) amortized and O(log n) worst case is a thing.