CODEWITHSUNDEEP
algorithm
venkysmarty
venkysmarty

Reputation: 11431

Regarding amortized analyis

This is regarding amortized analysis. Following is text from an article.

Amortized analyis for problems in which one must perform a series of operations, and our goal is to analyze the time per operation. The motivation for amortized analysis is that looking at the worst case time per operation can be too pessimistic if the only way to produce an expensive is to "set it up" with a a large number of cheap operations before hand.

Question: What does author mean by last statement i.e., "if the only way to produce an expensive is to "set it up" with a a large number of cheap operations before hand"? Can any one please explain with example what this statement mean?

Thanks!

Upvotes: 1

Views: 150

Answers (2)

Björn Pollex
Björn Pollex

Reputation: 76848

Another example. Consider an array that dynamically increases it's capacity when an element is added that exceeds the current capacity. Let increasing the capacity be O(n), where n is the old size of the array. Now, adding an element has a worst case complexity of O(n), because we might have to increase the capacity. The idea behind amortized analysis is that you have to do n simple adds that cost O(1) before the capacity is exhausted. Thus, many cheap operations lead up to one expensive operation. In other words, the expensive operation is amortized by the cheap operations.

Upvotes: 1

Simone
Simone

Reputation: 2311

The author means that the only way an expensive operation can occour is to be preceded by a big number of cheap operations.

Look at this example: We have a stack and we want the stack to implement in addition to the usual operations, also a operation called multipop(k) that pop k elements. Now, multipop costs O(min(n, k)), where n is the size of the stack; thus the prerequisite for the multipop to costs for example O(k) is to be precided by at least k cheap push each costing O(1).

Upvotes: 1

Related Questions