# What is amortized analysis of algorithm? How is it different from asymptotic analysis?

+1 vote
1,475 views
What is amortized analysis of algorithm? How is it different from asymptotic analysis?
posted Sep 22, 2014

+1 vote

Amortized:

An amortized analysis of algorithms is average of the time required to perform a sequence of data structure operations. The amortized analysis is different from the average case analysis, don't get confused with average case analysis. if we take the average of the sequence of operation, but there are the chances that a single operations cost may be expensive. Most common techniques of amortized analysis are:

``````   1. Aggregate Analysis
2. Accounting Method
3. Potential Method.
``````

Ex. Suppose we determine T(n) as an upper bound to the total cost of sequence of n operations then the average cost per operation T(n)/n is assigned to the each operation as an amortized cost.

Asymptotic Analysis

The asymptotic analysis is the time required by an algorithm to perform a data structure operation over the given data input. It is worst/average/best depends upon on the input.

Ex. A sorting algorithm might be O(nlogn).

Similar Questions

Example :
Let the list be {2,3,5} and Assume always 1 be included then

2th number is 2
3th number is 3
4th number is 4
5th number is 5
6th number is 6
7th number is 8
8th number is 9
9th number is 10
10th number is 12
11th number is 15 and so on...