in generalby adding up the amortized costs of all the rotationsof which at most one can be zigwe see that the total amortized cost to splay at node is at most (rf (xri ( ) where ri (xis the rank of before the first splaying step and rf (xis the rank of after the last splaying step since the last splaying step leaves at the rootwe obtain an amortized bound of ( (tri ( ) which is (log nbecause every operation on splay tree requires splaythe amortized cost of any operation is within constant factor of the amortized cost of splay thusall splay tree access operations take (log namortized time to show that insertions and deletions take (log )amortized timepotential changes that occur either prior to or after the splaying step should be accounted for in the case of insertionassume we are inserting into an - node tree thusafter the insertionwe have an -node treeand the splaying bound applies howeverthe insertion at the leaf node adds potential prior to the splay to each node on the path from the leaf node to the root let nk be the nodes on the path prior to the insertion of the leaf (nk is the root)and assume they have size sk after the insertionsthe sizes are + sk (the leaf will contribute to the potential so we can ignore it note that (excluding the root nodesj <sj+ so the new rank of nj is no more than the old rank of nj+ thusthe increase of rankswhich is the maximum increase in potential that results from adding new leafis limited by the new rank of the rootwhich is (log na deletion consists of nonsplaying step that attaches one tree to another this does increase the rank of one nodebut that is limited by log (and is compensated by the removal of nodewhich at the time was rootthus the splaying costs accurately bound the cost of deletion by using more general potential functionit is possible to show that splay trees have several remarkable properties this is discussed in more detail in the exercises summary in this we have seen how an amortized analysis can be used to apportion charges among operations to perform the analysiswe invent fictitious potential function the potential function measures the state of the system high-potential data structure is volatilehaving been built on relatively cheap operations when the expensive bill comes for an operationit is paid for by the savings of previous operations one can view potential as standing for potential for disasterin that very expensive operations can occur only when the data structure has high potential and has used considerably less time than has been allocated low potential in data structure means that the cost of each operation has been roughly equal to the amount allocated for it negative potential means debtmore time has been spent than has been allocatedso the allocated (or amortizedtime is not meaningful bound as expressed by equation ( )the amortized time for an operation is equal to the sum of the actual time and potential change taken over an entire sequence of operationsthe amortized time for the sequence is equal to the total sequence time plus the net change in potential as long as this net change is positivethen the amortized bound provides an upper bound for the actual time spent and is meaningful