Tell me more ×
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.
up vote 0 down vote favorite

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)

Thanks

share|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 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 at 1:18

1 Answer

up vote 0 down vote

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 http://en.wikipedia.org/wiki/Binomial_heap for example.

share|improve this answer

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.