Sign up ×
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.

This is my first question here. I was studying binomial heaps and it time analysis. Can there be any inputs that cause DELETE-MIN, DECREASE-KEY,and DELETE to run in Big-omega(log n) time for a binomial heap rather than Big-O(logn)


share|cite|improve this question
Welcome to MSE! Are you sure this is the right forum or did you want the Programmers SE? Regards – Amzoti Jan 16 '13 at 0:19
Actually, Computer Science.SE is probably the right place for this (not Programmers). This is squarely within the scope of CS.SE. – D.W. Jan 16 '13 at 1:18

1 Answer 1

All those operations take $\Theta(\log n)$ time which is both $O(\log n)$ and $\Omega(\log n)$ time. Did you mean $\omega(\log n)$? In which case the answer is no for the reason I just gave. See chapter 20 of CLRS or for example.

share|cite|improve this answer

Your Answer


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.