Maximum time of Extract-Min - Fibonacci heap

Question

What is the actual maximum time of executing extract-min on n-element Fibonacci heap?

Is it O(D(n) + t(H)), where D(n) = lg*n is the maximum degree of a node in n-element heap and t(H) = O(n) is a number of roots in heap H?

Does this mean that answer for question above is actually O(n) = Theta(n)? If no, please correct my thinking and answer.

Answer 1

You're correct -- the maximum time complexity of a single call to deleteMin is O(n). The lower O(logn) bound on the operation is its amortized time complexity, and is the same between the best case and the worst case.