Which amortized analysis technique uses a function to represent the 'stored energy' or 'prepaid work' of a data structure?
Show answer
The potential method
The potential method defines a potential function that maps the state of a data structure to a non-negative real number. It is used to prove that the average cost of an operation is low, even if a single operation is expensive.
Also asked as:
- Which method of amortized analysis maps the state of a data structure to a non-negative real number to represent its potential?