amortized analysis because it is well known that the fibonacci numbers grow exponentiallyit immediately follows that any node with descendants has rank at most (log sthuswe have lemma the rank of any node in fibonacci heap is (log nproof immediate from the discussion above if all we were concerned about were the time bounds for the mergeinsertand deletemin operationsthen we could stop here and prove the desired amortized time bounds of coursethe whole point of fibonacci heaps is to obtain an ( time bound for decreasekey as well the actual time required for decreasekey operation is plus the number of cascading cuts that are performed during the operation since the number of cascading cuts could be much more than ( )we will need to pay for this with loss in potential if we look at figure we see that the number of trees actually increases with each cascading cutso we will have to enhance the potential function to include something that decreases during cascading cuts notice that we cannot just throw out the number of trees from the potential functionsince then we will not be able to prove the time bound for the merge operation looking at figure againwe see that cascading cut causes decrease in the number of marked nodesbecause each node that is the victim of cascading cut becomes an unmarked root since each cascading cut costs unit of actual time and increases the tree potential by we will count each marked node as two units of potential this waywe have chance of canceling out the number of cascading cuts theorem the amortized time bounds for fibonacci heaps are ( for insertmergeand decreasekey and (log nfor deletemin proof the potential is the number of trees in the collection of fibonacci heaps plus twice the number of marked nodes as usualthe initial potential is and is always nonnegative thusover sequence of operationsthe total amortized time is an upper bound on the total actual time for the merge operationthe actual time is constantand the number of trees and marked nodes is unchangedsoby equation ( )the amortized time is ( for the insert operationthe actual time is constantthe number of trees increases by and the number of marked nodes is unchanged thusthe potential increases by at most so the amortized time is ( for the deletemin operationlet be the rank of the tree that contains the minimum elementand let be the number of trees before the operation to perform deleteminwe once again split the children of treecreating an additional new trees notice thatalthough this can remove marked nodes (by making them unmarked roots)this cannot create any additional marked nodes these new treesalong with the other treesmust now be mergedat cost of log (log )by lemma since there can be at most (log ntreesand the number of marked nodes cannot