Re:Why databases use ordered indexes but programming uses ha...
by ajuc on Tuesday December 10, 2019 @05:38AM
(#21751317)
> 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.
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.