# Why isn't the decrease key operation in a pairing heap $O(1)$

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.