Amortized Analysis | Aggregate Analysis

Amortized Analysis

In an Amortized Analysis, the time required to perform a sequence of data-structure operations is averaged over all the operations performed. Amortized analysis can be used to show that the average cost of an operation is small, if one averages over a sequence of operations, even though a single operation might be expensive. Amortized analysis differs from average-case analysis in that probability is not involved; an amortized analysis guarantees the average performance of each operation in the worst case.

  1. The amortized cost of an operation is the total cost charged to the
  2. No involvement of
  3. Average performance on a sequence of operations, even some operation is expensive.
  4. This reduces charged cost of some operations and increases that of the
  5. Guarantee average performance of each operation among the sequence in worst
  6. Amortized analysis is also used to estimate the time complexity of

There are several techniques used in amortized analysis 

  1. Aggregate analysis: It determines the upper bound T(n) on the total cost of a sequence of n operations, then calculates the average cost to be T(n)/n. In the aggregate method of amortized analysis, we show that for all n,  a  sequence  of n operations  takes worst- case time T(n) in In the worst case, the average cost, or amortized cost, per operation is therefore T(n) / n. Note that this amortized cost applies to each operation, even when there are several types of operations in the sequence. The other two methods we shall study in this chapter, the accounting method and the potential method, may assign different amortized costs to different types of operations.
  2. Accounting method: It determines the individual cost of each operation, combining its immediate execution time and its influence on the running time of future In the accounting method of amortized analysis, we assign differing charges to different operations, with some operations charged more or less than they actually cost. The amount we charge an operation is called its amortized cost. When an operation’s amortized cost exceeds its actual cost, the difference is assigned to specific objects in the data structure as credit. Credit can be used later on to help pay for operations whose amortized cost is less than their actual cost. Thus, one can view the amortized cost of an operation as being split between its actual cost and credit that is either deposited or used up. This is very different from the aggregate method, in which all operations have the same amortized cost.
  3. Potential method: It is like the accounting method, but overcharges operations early to compensate for undercharges
    1. Idea is to overcharge some operations and store the overcharge as credits/potential which can then help pay for later operations (making them cheaper).
    2. Leads to equivalent but slightly different definition of amortized Consider performing n operations on an initial data structure D0

Di is data structure after ith operation, i = 1, 2, . . . , n.
ci is actual cost (time) of ith operation, i = 1, 2, . . . , n.

Amortized Analysis

Topic : Amortized Analysis | Amortized Analysis

This Article is contributed by Karthik Alapati. if you find any mistake please comment below in comment section

Leave a Reply