I was studying binomial heaps and its time analysis. Are there any inputs that cause DELETE-MIN, DECREASE-KEY, and DELETE to run in $\Omega(\log n)$ time for a binomial heap rather than $O(\log n)$?

  • $\begingroup$ On a small technical note, $T(n)\in \Omega(f(n))$ doesn't preclude $T(n) \in O(f(n))$. $\endgroup$ – Luke Mathieson Jan 16 '13 at 8:09

This paper shows that for each priority queue implementation satisfying some technical condition (which holds for binomial heaps) there is a sequence of operations consisting of $n$ INSERTs, $n$ DELETEs and $n$ FIND-MINs that takes time $\Omega(n\log n)$. Since INSERTs are amortized $O(1)$ in binomial heaps, the DELETEs and FIND-MINs together must take time $\Omega(n\log n)$. Unfortunately, in the construction the INSERTs are interspersed between the other operations.

This is of course overkill for the case of binomial heaps.In the implementation in which FIND-MIN is implemented by comparing the roots of all trees. If we INSERT $2^m-1$ elements then we will have $m = \log(n+1)$ trees, and so FIND-MIN will take time $\Omega(\log n)$. In other implementations, it shouldn't be hard to concoct examples in which some MERGE operation (used inside all the others) takes time $\Omega(\log n)$.

You might be worried that even though these examples show that some operations could require logarithmic time, the amortized complexity is still better. You'll have to work harder, but after some though you should be able to come up with a sequence of $n$ INSERTs and DELETEs which takes amortized time $\Omega(\log n)$.

  • $\begingroup$ thanks for the reply... Can you please provide me some inputs that cause these operations in Ω(logn). $\endgroup$ – Wearybands Jan 16 '13 at 20:40
  • $\begingroup$ @Umair, I suspect that this is a homework question, and I am not going to solve your homework for you. $\endgroup$ – Yuval Filmus Jan 16 '13 at 20:45
  • $\begingroup$ Well I tried to find some inputs but could not. Can u just give me a hint / $\endgroup$ – Wearybands Jan 16 '13 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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