68. What are the aggregate, accounting and potential methods of amortized analysis?
HardAlgorithm analysis
Show model answer
Aggregate: bound the total cost of any sequence of n operations and divide by n (as with the doubling array). Accounting: charge each operation a fixed "price" that may exceed its real cost; the surplus is stored as credit on data elements and pays for expensive operations later, and you must show the credit never goes negative. For the doubling array, charging 3 per append works: 1 for the write and 2 saved to pay for copying that element and one older element at the next resize.
Potential: define a function Φ of the data structure state, with Φ(initial) = 0 and Φ >= 0 always. Amortized cost = actual cost + ΔΦ. A common choice for the array is Φ = 2·size - capacity. Cheap appends raise Φ by 2 and a resize releases enough potential to cancel the copy. The same methods analyse a binary counter increment (O(1) amortized) and a two-stack queue.