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:
“Protestantism has the method of Jesus with His secret too much left out of mind; Catholicism has His secret with His method too much left out of mind; neither has His unerring balance, His intuition, His sweet reasonableness. But both have hold of a great truth, and get from it a great power.”
—Matthew Arnold (1822–1888)
“in the absence of feet, “a method of conclusions”;
“a knowledge of principles,”
in the curious phenomenon of your occipital horn.”
—Marianne Moore (1887–1972)