Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need some help with the following problem from Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein:

Consider an ordinary binary min-heap data structure with $n$ elements that supports 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 he amortized cost of EXTRACT-MIN is $O(1)$, and show that it works.

I'm not sure how to define the potential here. Especially since everything looks so "symmetric".

I mean, I get that one can only do as many EXTRACT-MIN operations as one does INSERT operations, and so if we have $k$ INSERT operations and $\ell$ EXTRACT-MIN operations total, then the time this takes is surely not bigger than doing the INSERT first and the EXTRACT-MIN operations later. And so I guess, the time for all operations is

$$ \begin{align} t(k+\ell) &\le (\lg 1 + \lg 2 + \dots + \lg k) + (\lg k + \lg (k-1) + \dots + \lg (k-\ell+1)) \\ &= 2\lg k! - \lg \ell! \\ &= O(k\lg k) \end{align} $$

Hence we can assign $O(\lg k)$ to every insert operation and $O(1)$ to every EXTRACT-MIN operation (?).

So the result at least makes some sense. But I still don't know how to do it formally using a potential.

Thanks for your help! =)

share|improve this question
add comment

migrated from scicomp.stackexchange.com Jan 22 '12 at 13:02

This question came from our site for scientists using computers to solve scientific problems.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.