I have got the following answer but not satisfied me, Can you widen and if possi

Question

I have got the following answer but not satisfied me, Can you widen and if possible give some small examples. Thanks.

Amortized analysis is a worst-case analysis of a a sequence of operations to obtain a tighter bound on the overall or average cost per operation in the sequence than is obtained by separately analyzing each operation in the sequence. It is more useful than the worst case when an occasional operation is very slow, but most of the other operations are faster.

4. Explain what amortized cost analysis is, and when it is helpful when compared to worst case analysis of individual operations. You can use the example of coupons that I gave in your explanation.

Explanation / Answer

Answer:

Let me give an example :

In Table Doubling in Hash tables :

So this is the total time taken by Table doubling , but in Amortized analysis we analyze the overall time cost of each operation in an algorithm. Now let me give the general definition of amortized analysis :

" Assign a cost for each operation ( the cost is called amortized cost) such that you preserve the sum to each cost.

sum of amortized cost = > sum of actual cost.

Example :

2-3 trees achieve O(1) worst case per "create-empty'.

O(logn*) per insert

phi per delete .

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.