top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

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

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+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).

answer Oct 2, 2014 by Prakash Singh
Similar Questions
+5 votes

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...

+2 votes

Assume priority queue in Dijkstra’s algorithm is implemented using a sorted link list and graph G (V, E) is represented using adjacency matrix.

What is the time complexity of Dijkstra’s algorithm (Assume graph is connected)?

+3 votes

What data structure would you mostly likely see in a non recursive implementation of a recursive algorithm?

...