increasethe potential change is at most (log nt adding the actual time and potential change gives the (log namortized bound for deletemin finallyfor the decreasekey operationlet be the number of cascading cuts the actual cost of decreasekey is which is the total number of cuts performed the first (noncascadingcut creates new tree and thus increases the potential by each cascading cut creates new tree but converts marked node to an unmarked (rootnodefor net loss of one unit per cascading cut the last cut also can convert an unmarked node (in fig it is node into marked nodethus increasing the potential by the total change in potential is thus at most adding the actual time and the potential change gives total of which is ( splay trees as final examplewe analyze the running time of splay trees recallfrom that after an access of some item is performeda splaying step moves to the root by series of three operationszigzig-zagand zig-zig these tree rotations are shown in figure we adopt the convention that if tree rotation is being performed at node xthen prior to the rotationp is its parent and (if is not child of the rootg is its grandparent recall that the time required for any tree operation on node is proportional to the number of nodes on the path from the root to if we count each zig operation as one figure zigzig-zagand zig-zig operationseach has symmetric case (not shown