amortized analysis rotation and each zig-zig or zig-zag as two rotationsthen the cost of any access is equal to plus the number of rotations in order to show an (log namortized bound for the splaying stepwe need potential function that can increase by at most (log nover the entire splaying step but that will also cancel out the number of rotations performed during the step it is not at all easy to find potential function that satisfies these criteria simple first guess at potential function might be the sum of the depths of all the nodes in the tree this does not workbecause the potential can increase by (nduring an access canonical example of this occurs when elements are inserted in sequential order potential function that does work is defined as log ( (tit where (irepresents the number of descendants of (including itselfthe potential function is the sumover all nodes in the tree tof the logarithm of (ito simplify the notationwe will define (ilog (ithis makes ( (iit (irepresents the rank of node the terminology is similar to what we used in the analysis of the disjoint set algorithmbinomial queuesand fibonacci heaps in all these data structuresthe meaning of rank is somewhat differentbut the rank is generally meant to be on the order (magnitudeof the logarithm of the size of the tree for tree with nodesthe rank of the root is simply (tlog using the sum of ranks as potential function is similar to using the sum of heights as potential function the important difference is that while rotation can change the heights of many nodes in the treeonly xpand can have their ranks changed before proving the main theoremwe need the following lemma lemma if <cand and are both positive integersthen log log < log proof by the arithmetic-geometric mean inequalityab <( )/ thusab < /