<p>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:</p>

<blockquote>
  <p>Decrease-key and insertion operations are both considered to have 0 <em>actual</em> cost.</p>
</blockquote>

CC BY-SA 3.0
2013-10-01T14:11:37.643Z
2013-10-01T14:11:37.643Z
jbapple
<p>According to the <a href="http://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf" rel="nofollow">paper (1986)</a></p>

<p>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.</p>

<p>I must be missing something since <a href="http://wwwens.uqac.ca/azinflou/Fichiers840/EfficiencyPairingHeap.pdf" rel="nofollow">this paper</a> shows that it is $\Omega(\log \log n)$ amortized.</p>

<ds.data-structures>
Why isn't the decrease key operation in a pairing heap $O(1)$
dpington
# Why isn't the decrease key operation in a pairing heap $O(1)$

(Asked by: username_0 on 2013-10-01)

According to the [paper (1986)](http://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf)

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](http://wwwens.uqac.ca/azinflou/Fichiers840/EfficiencyPairingHeap.pdf) shows that it is $\Omega(\log \log n)$ amortized.

**Tags:** ds.data-structures


---

## 1 answers

### Answer by username_1 on 2013-10-01. Score: 3 | Accepted answer

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.


---

