What is Amortized Analysis or Amortized Complexity

Amortized Analysis or Amortized Complexity

In an amortized analysis we average the time required perform a sequence of data structure operations over all operations perform. 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 guaranties average performance of each operations in the worst case unlike the actual best, average and worst case complexities of an operation, which are closely related to step count for that operation, the amortized complexity of an operation is an accounting artifact that often bears no direct relationship to the actual complexity of that operation. The amortized complexity of an operation could be anything. The only requirement is that the sum of the amortized complexities of all operations in sequence of operations be greater than or equal to their sum of actual complexities. That is -}

………(1)

Where amortized(i) and actual(i) respectively denotes the amortized and actual complexities of i^th operation in a sequence of n operations, because of this requirement on the sum of the amortized complexities of operations in any sequence of operations. We may use the sum of the amortized complexities as an upper bound on the complexity of any sequence of operation. We may view the amortized cost of an operation as being the amount we charge the rather than the amount of the operation cost. We can charge an operation any amount we wish as long as the amount charge to all operations in the sequence at least equal to the actual cost of the operation sequence.

·         Potential Function:

Relative to the actual and amortized cost of each operation in a sequence of n operations, we define a potential function p(i) as follows –

P(i)= amortized(i) – actual(i) + p(i-1) ……….(2)

That is the i^th operation cause the potential function to change by the difference between the amortized and the actual cost of that operation.

 If we sum equation (2) for we get,

Under the assumption that P(0)=0 the potential P(i) is the amount by which the first I operations have been over charged.