Consider an ordinary binary min-heap data structure with n elements supporting the instructions INSERT and EXTRACT-MIN in O($\lg n)$ worst-case time. Give a potential function $\Phi$ such that the amortized cost of INSERT is $O(\lg n)$ and the amortized cost of EXTRACT-MIN is $O(1)$.

I try to solve it, but I got in stuck:

Let $c_i$ denotes real cost of $i-th$ operation, and $a_i$ denotes amortized cost.
Let $\Phi(D_i) = \text{number of elements after i operations}$
INSERT:$$a_i=c_i+ \Phi(D_i) - \Phi(D_{i-1}) \le \log(i) + (i)\log(i) - (i-1)\log(i-1) \le 3\log(i+1) = O(\log(i))$$
EXCTRACT-MIN:$$ a_i=c_i + \Phi(D_i) - \Phi(D_{i-1}) \le \log(i) + i\log(i) - (i+1)\log(i+1) =\log(i) + i\log(i) - i\log(i+1) - \log(i+1) < 0 $$

As you can see, my problem is that I get number lower than $0$. Can you help me ?

  • $\begingroup$ Where are you getting that that $\Phi(D_i) = i\log(i)$, if it's the number of elements? How can I have $i\log(i)$ elements after $i$ operations? $\endgroup$ Sep 3 '15 at 12:21
  • $\begingroup$ Ok, It was not OK. My potential function is number of nodes. $\endgroup$
    – M.Swe
    Sep 3 '15 at 12:23
  • $\begingroup$ OK. In that case, please edit your question to adjust it and fix the error. Don't just leave clarifications in the comments: edit your question to correct any mistakes/ambiguities/etc. Questions should be self-contained -- people shouldn't have to read the comments to understand your question -- and comments can disappear at any time. $\endgroup$
    – D.W.
    Sep 3 '15 at 17:03

Let's review the potential function method. Suppose that the $i$th operation costs $c_i$ and the value of the potential function at time $i$ is $\Phi_i \geq 0$, and that $\Phi_0 = 0$ (the potential at the beginning). Define the amortized operation costs by $a_i = c_i + \Phi_i - \Phi_{i-1}$. Then $$ \sum_{i=1}^n a_i = \sum_{i=1}^n (c_i + \Phi_i - \Phi_{i-1}) = \sum_{i=1}^n c_i + \Phi_n - \Phi_0 \geq \sum_{i=1}^n c_i. $$ This means that the total amortized cost $\sum_{i=1}^n a_i$ is an upper bound on the actual cost $\sum_{i=1}^n c_i$, which is what we want.

In this argument there is no need to assume that the amortized costs are non-negative – the argument works even if they can be negative. However, if some amortized costs are negative, then you can probably improve the amortized analysis.

Back to your case. Suppose that inserting the $n$ element costs $\log n$, and extracting the minimum when there are $n$ elements also costs $\log n$. This suggests a charging argument in which we charge the insertion of the $n$th element by $2\log n$, and discharge the extra $\log n$ when extracting the minimum the next time that there are exactly $n$ elements. This gives an amortized time of $O(\log n)$ for insertion, and $0$ for extract-min.

We can give a similar argument using a potential function. We choose a potential function of the form $\sum_{i=1}^n \log i$, where $n$ is the current number of elements. Under this potential function, insertion costs $2\log n$ and extract-min costs $0$.

Note that $\sum_{i=1}^n \log i = \log n! \approx n\log n$, so this differs from your suggestion (appearing in the comments) of using $n$ as a potential function; your suggestion doesn't work, since under it extract-min costs $$ \log n + n - (n-1) = \log n - 1. $$ Taking a closer look at your question, you are actually using the potential function $n\log n$, which is very similar to what I suggest. This potential function does work.


Your Answer

