Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 17

The authors discuss amortized analysis where time required to perform a sequence of operations on a data structure is averaged over all the operations performed. The insight into an amortized data structure gained by performing amortized analysis can help in optimizing the design of the data structure. The authors discuss three methods to determine the amortized cost of each operation as follows:

• Aggregate analysis: In this method, the worst case time for sequence of $n$ operations is shown to be $T(n)$ in total and so the amortized cost is $T(n)/n$. The authors create a new operation MULTIPOP(S, k) on stack which removes $k$ items from the top of the stack and find that even though the total cost of MULTIPOP is $ min(s, k) $, where $s$ is the number of items in the stack, a sequence of $n$ PUSH, POP or MULTIPOP operations result in time complexity of only $O(n)$. The amortized cost of $n$ PUSH, POP and MULTIPOP operations is $O(n)/n = O(1)$. The authors also provide an example of a binary counter and prove that the total cost of $n$ INCREMENT operations on the counter is $O(n)$ and thus amortized cost is $O(n)/n=O(1)$.
  
• Accounting method: In this method, different operations are assigned differing charges with some operations charged more or less than they actually cost. When the amortized cost exceeds the actual cost, the difference is credited to elements in the data structure that later can be used to pay for operations whose amortized cost is less than the actual cost. The authors analyze both the stack and binary counter operations with this method to conclude that the total amortized cost of $n$ operations in both the cases is $O(n)$.
  
• Potential method: In this method, the credit is stored as a "potential energy" with the data structure as a whole instead of with elements of the data structure. The authors analyze both the stack and binary counter operations with this method.
  

The authors then discuss the problem of table expansion/contraction with INSERT and DELETE operations and prove that the total amortized cost of $n$ operations is $O(n)$.