algorithmdata-structurescomplexity-theoryamortized-analysisfibonacci-heap

Amortized Analysis of Fibonacci Heap with Potential Method

I'm trying to do an amortized analysis of a fibonacci heap using the potential method. I'm struggling with understanding the analysis of the pop min / delete min operation.

In tutorials I can find for bounding the amortized complexity of the "pop min" operation, such as this one, the tutorial authors set the potential to "phi(fib heap) = number of root nodes + 2 * number of loser nodes" . They then analyse the popmin operation in its two steps:

  1. In the first step, it deletes the minimum node and puts the minimum node's children on the root list. By analysis on the trees (the fact that no node is allowed to lose more than one child), you know that this will take only O(log n) operations. This part I understand.

  2. In the second step, you perform cleanup by merging all trees of the same size iteratively. This is where, to me, the analysis gets confusing:

In amortized analysis, the cost is always "real cost + change in potential". They analyze the real cost to be O(t + m + d) -- the m figure is the number of merges, and the d figure is the number of trees after the merge, while the t figure is the number of nodes before the cleanup from when you do a linear scan over the root list. The change in potential is bound above by -m -- the root list size decreases by the number of merges. t = m + d, so the operation is O(m + d). So far, I am following.

Then, in the tutorial linked, he adds the change in potential to O(m + d) to get O(m + d) - m = O(d) ... This makes no sense! I'm fairly certain that, by the definition of big O, that is impossible. Nevertheless, that remains his justification for the amortized cost of the popmin operation in the video.

Can anybody explain what he means by O(m + d) - m, or if not, a way of analyzing the popmin operation in the fibonacci heap to get an amortized runtime of O(log n) ?

Solution

  • I discovered the answer in this video around mark 30:35. He states that you simply take the maximum value of all of the constants of the amortized operations hidden by their big O, and multiply it into the potential function.