It reminds me of the hash maps that are said to be amortized O(1) but can be O(n) for some sequences of operations in various languages like Python and JS: https://blog.toit.io/hash-maps-that-dont-hate-you-1a96150b49...