proposition let be splay tree with root and let be the total variation of ( caused by splaying node at depth we have < ( (tr( ) justificationsplaying node consists of / splaying substepseach of which is zig-zig or zig-zagexcept possibly the last onewhich is zig if is odd let (xr(xbe the initial rank of xand for clet ri (xbe the rank of after the ith substep and di be the variation of ( caused by the ith substep by proposition the total variation of ( caused by splaying is di = < (ri (xri- ( ) = (rc (xr ( ) < ( (tr( ) by proposition if we make payment of ( (tr( ) cyber-dollars towards the splaying of node xwe have enough cyber-dollars to maintain the invariantkeeping (wcyber-dollars at each node in and pay for the entire splaying workwhich costs cyber-dollars since the size of the root is nits rank (tlog given that ( > the payment to be made for splaying is (log ncyber-dollars to complete our analysiswe have to compute the cost for maintaining the invariant when node is inserted or deleted when inserting new node into splay tree with keysthe ranks of all the ancestors of are increased namelylet wi wd be the ancestors of wwhere wwi is the parent of wi- and wd is the root for dlet (wi and (wi be the size of wi before and after the insertionrespectivelyand let (wi and (wi be the rank of wi before and after the insertion we have (wi (wi alsosince (wi < (wi+ )for we have the following for each in this ranger (wi log( (wi )log( (wi <log( (wi+ ) (wi+ thusthe total variation of ( caused by the insertion is (wi (wii= - < (wd ( (wi+ (wi ) = (wd ( <log thereforea payment of (log ncyber-dollars is sufficient to maintain the invariant when new node is inserted