5 ms·
O(1) insertion is the amortized worst-case time complexity, actually. (Amortized in the sense that the O(n) cost of copying is paid only during the n-th inserti
by lou1306 6d ago
O(1) insertion is the amortized worst-case time complexity, actually. (Amortized in the sense that the O(n) cost of copying is paid only during the n-th insertion). Average complexity is a slightly different thing.
- d0mine 5d agoIt is not “worst-case” (as the post demonstrates, you can get worse results by using specifically crafted data that exploits hash collisions). There are algorithms that can get you O(logN) instead of O(N) even on such data.