> checking for key existence is generally only amortized constant (that is to say, not constant across all lookups) What you just described is "average" not "a

> checking for key existence is generally only amortized constant (that is to say, not constant across all lookups) What you just described is "average" not "amortized". Amortized does not mean "across a set of representative inputs", it means "through time, even if given the same input repeatedly". Amortized complexity is tricky sometimes. For instance, in a data structure storing a binary integer and allowing an increment operation, the number of bits flipped is amortized O(1). The same is true if the only operation is decrement. Neither is true if you have both increment and decrement! Another example: you can change the accounting to make things amortized lower cost. For instance, a heap (aka implicit priority queue) can be said to have O(1) deleteMin by simply ascribing an extra O(log n) cost to each insert. In fact, you can say deleteMin has O(0) cost! An example of this being done in the literature is https://arxiv.org/abs/0903.4130 https://arxiv.org/abs/0903.4130, "Pairing Heaps with Costless Meld", by Amr Elmasry.