Method of analyzing the amortized complexity of a data structure
In computational complexity theory , the potential method is a method used to analyze the amortized time and space complexity of a data structure , a measure of its performance over sequences of operations that smooths out the cost of infrequent but expensive operations.[ 1] [ 2]
^ Goodrich, Michael T. ; Tamassia, Roberto (2002), "1.5.1 Amortization Techniques", Algorithm Design: Foundations, Analysis and Internet Examples , Wiley, pp. 36–38 .
^ Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990]. "17.3 The potential method". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 412–416. ISBN 0-262-03293-7 .