squaring both sides gives ab < / taking logarithms of both sides proves the lemma with the preliminaries taken care ofwe are ready to prove the main theorem theorem the amortized time to splay tree with root at node is at most ( ( )- ( ))+ (log nproof the potential function is the sum of the ranks of the nodes in if is the root of tthen there are no rotationsso there is no potential change the actual time is to access the nodethusthe amortized time is and the theorem is true thuswe may assume that there is at least one rotation for any splaying steplet ri (xand si (xbe the rank and size of before the stepand let rf (xand sf (xbe the rank and size of immediately after the splaying step we will show that the amortized time required for zig is at most (rf (xri ( ) and that the amortized time for either zig-zag or zig-zig is at most (rf (xri ( )we will show that when we add over all stepsthe sum telescopes to the desired time bound zig stepfor the zig stepthe actual time is (for the single rotation)and the potential change is rf (xrf (pri (xri (pnotice that the potential change is easy to computebecause only ' and ' trees change size thususing at to represent amortized timeatzig rf (xrf (pri (xri (pfrom figure we see that si ( >sf ( )thusit follows that ri ( >rf (pthusatzig < rf (xri (xsince sf ( >si ( )it follows that rf (xri ( > so we may increase the right sideobtaining atzig < (rf (xri ( )zig-zag stepfor the zig-zag casethe actual cost is and the potential change is rf (xrf (prf (gri (xri (pri (gthis gives an amortized time bound of atzig-zag rf (xrf (prf (gri (xri (pri (gfrom figure we see that sf (xsi ( )so their ranks must be equal thuswe obtain atzig-zag rf (prf (gri (xri (