> that seems an abuse of big-O notation Formally it's amortized O(1) time and pessimistic O(n) time. It's not abuse - many algorithms and data structures have

> that seems an abuse of big-O notation Formally it's amortized O(1) time and pessimistic O(n) time. It's not abuse - many algorithms and data structures have different performance in average and worst case - for example quicksort is O(n log n) but in worst case it's O(n^2). People just ignore the worst case unless worst-case guarantees are especially important for their system.