According to the paper (1986)

Decrease-key is implemented by first by removing the node from the tree $O(1)$, decreasing the key $O(1)$, then linking it with the root node $O(1)$. The paper admits this as well.

I must be missing something since this paper shows that it is $\Omega(\log \log n)$ amortized.


1 Answer 1


An operation can have higher amortized cost than actual cost if it adds too many coins (in the banker's method) or too much potential (in the physicist's method). The lower bound paper you linked to includes the line:

Decrease-key and insertion operations are both considered to have 0 actual cost.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.