Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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)$?

share|improve this question
    
On a small technical note, $T(n)\in \Omega(f(n))$ doesn't preclude $T(n) \in O(f(n))$. –  Luke Mathieson Jan 16 '13 at 8:09

1 Answer 1

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)$.

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

Your Answer

 
discard

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

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