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:
“The method of painting is the natural growth out of a need. I want to express my feelings rather than illustrate them. Technique is just a means of arriving at a statement.... I can control the flow of paint: there is no accident, just as there is no beginning and no end.”
—Jackson Pollock (1912–1956)
“One of the grotesqueries of present-day American life is the amount of reasoning that goes into displaying the wisdom secreted in bad movies while proving that modern art is meaningless.... They have put into practise the notion that a bad art work cleverly interpreted according to some obscure Method is more rewarding than a masterpiece wrapped in silence.”
—Harold Rosenberg (1906–1978)