The Method
Preliminarily, we choose a set of elementary operations which will be used in the algorithm, and arbitrarily set their cost to 1. The fact that the costs of these operations may in reality differ presents no difficulty in principle. What is important, is that each elementary operation has a constant cost.
Each aggregate operation is assigned a "payment". The payment is intended to cover the cost of elementary operations needed to complete this particular operation, with some of the payment left over, placed in a pool to be used later.
The difficulty with problems that require amortized analysis is that, in general, some of the operations will require greater than constant cost. This means that no constant payment will be enough to cover the worst case cost of an operation, in and of itself. With proper selection of payment, however, this is no longer a difficulty; the expensive operations will only occur when there is sufficient payment in the pool to cover their costs.
Read more about this topic: Accounting Method
Famous quotes containing the word method:
“Direct action ... is the logical, consistent method of Anarchism.”
—Emma Goldman (1869–1940)
“Argument is conclusive ... but ... it does not remove doubt, so that the mind may rest in the sure knowledge of the truth, unless it finds it by the method of experiment.... For if any man who never saw fire proved by satisfactory arguments that fire burns ... his hearer’s mind would never be satisfied, nor would he avoid the fire until he put his hand in it ... that he might learn by experiment what argument taught.”
—Roger Bacon (c. 1214–1294)