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.
Maximum time of Extract-Min - Fibonacci heap
-
09-10-2022 - |
Domanda
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.
Soluzione
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow