Amortized Analysis

Click here to Download PDF for this Topic

 

Amortized Analysis

In an Amortized Analysis, we average the time required to perform a sequence of data-structure operations over all the operations performed. With amortized analysis, we can show that the average cost of an operation is small, if we average over a sequence of operations, even though a single operation within the sequence 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 Average Cost in Worst Case! 

1) Aggregate Analysis: In Aggregate Analysis, we show that for all n, a sequence of n operations takes worst-case time T(n) in total. In the worst case, the average cost, or amortized cost, per operation is therefore T(n) / n[1].

This amortized cost applies to each operation, even when there are several types of operations in a sequence. This method is less precise than other methods, as all operations are assigned the same cost [2].

Example: Please refer PDF given here for example

therefore O(n), so the amortized cost of each operation is O(n)/n = O(1) [2].

2) Accounting Method: In Accounting Method, we assign different charges to different operations. Some operations may be charged more than their actual cost while some operations may be charged less than their actual cost.

The amount we charged to an operation is Amortized Cost. In Accounting Method, the amount charged for each operation type is Amortized Cost for that type of operations. When Amortized Cost is more than Actual Cost, then remaining cost after operation, is credited, and if Amortized Cost is less than Actual Cost, then credit is used from stored.

Picking the appropriate charges for a particular operation is the key to successful Amortized Analysis.

If we denote the actual cost of the i^th operation by ci and the amortized cost of the i^th operation by ^c, then we require

 

Example: Please refer PDF given here for example

3) Potential Method: In Potential Method, it stores pre-payments as potential or potential energy that can be released to pay for future operations. The stored potential is associated with the entire data structure rather than specific objects within the data structure.

Working:

·         D₀ is the initial data structure (e.g., stack)

·         D_i is the data structure after the i^th operation.

·         C_i is the actual cost of the i^th operation.

·         The potential function Φ maps each D_i to its potential value Φ(D_i)

The amortized cost ^{^}c_i of the i^th operation w.r.t potential function Φ is defined by

^{^}c_i   = c_i + Φ(D_i) - Φ(D_i-1)

Where, c_i + Φ(D_i) - Φ(D_i-1) = Change in potential due to the operation

Further explanation is given in PDF...

Click here to Download PDF for this Topic