amortized analysis if we ignore the constant in the big-oh notationby the argument above once this is donethere can be at most log trees remainingso the potential function can increase by at most (log nt adding the actual time and the change in potential gives an amortized bound of log since all the trees are binomial treeswe know that <log thus we arrive at an (log namortized time bound for the deletemin operation the fibonacci heap operations as we mentioned beforethe fibonacci heap combines the leftist heap decreasekey operation with the lazy binomial queue merge operation unfortunatelywe cannot use both operations without slight modification the problem is that if arbitrary cuts are made in the binomial treesthe resulting forest will no longer be collection of binomial trees because of thisit will no longer be true that the rank of every tree is at most log since the amortized bound for deletemin in lazy binomial queues was shown to be log rwe need (log nfor the deletemin bound to hold in order to ensure that (log )we apply the following rules to all non-root nodesr mark (non-rootnode the first time that it loses child (because of cutr if marked node loses another childthen cut it from its parent this node now becomes the root of separate tree and is no longer marked this is called cascading cutbecause several of these could occur in one decreasekey operation figure shows one tree in fibonacci heap prior to decreasekey operation when the node with key is changed to the heap order is violated thereforethe node is cut from its parentbecoming the root of new tree since the node containing is markedthis is its second lost childand thus it is cut from its parent ( now has figure tree in the fibonacci heap prior to decreasing to we can do this because we can place the constant implied by the big-oh notation in the potential function and still get the cancellation of termswhich is needed in the proof