Amortized cost analysis

[humor_me]

I recently came across an amortized cost analysis problem where one was asked to find the cost of a total of n operations on average. Does that mean that the problem is asking for the average cost of each operation or is it referring to the total cost of n operations? The wording is kind of confusing.

[Zachm]

I recently came across an amortized cost analysis problem where one was asked to find the cost of a total of n operations on average. Does that mean that the problem is asking for the average cost of each operation or is it referring to the total cost of n operations? The wording is kind of confusing.

The word "total" eliminates the confusion. The cost is a total cost.
If you take m possible sets, Si of n operations each,
and for each i compute the total cost C(Si), then your average is:

sum{i=1..m}( C(Si) ) / m

I hope I'm being understood ...

Regards,
Zachm

[humor_me]

Makes sense. So, if there was some operation performed on a data structure and the amortized cost of each such operation was O(1), and the cost of a total of n operations in the worst case is O(n), the cost of a total of n operations on average would also be O(n), correct?

HM

[Zachm]

The average case costs at most as the worst case, since it is the worst case,
Yes, it would also be O(n) but maybe you can find a lower bound.

For example, quicksort algorithm performs k = O(n^2) operations but on average it performs only k = O(n log n) operations, which is also = O(n^2) operations.

Regards,
Zachm

[humor_me]

That was very helpful. Thank you for your response. If each operation takes ATLEAST constant time and i assume any operation would have to, and we repeat that operation n times, is it possible that the average case time have a better lower bound than O(n)?

Regards,
HM

[Zachm]

If each operation takes ATLEAST 1 time unit (and not O(1) - which means it can take 0 time units or 1000000 time units as well), then any set of n such operations will take ATLEAST n time units, and specifically the average time of n such operations will take ATLEAST n time units. This is common sense.

The weird part happens when you introduce the Big-Oh notation - which is used to mark asymptotic upper bound, it doesn't say anything on any single specific set of operations - mathematically speaking, they might even take 0 time.
That being said, it is common practice that any algorithm constant time operation takes at least 1 time unit (maybe more - O(1) time units).

If you assume each operation takes some time then you can't find a lower bound smaller than O(n).

Usually when you are requested to find the average cost of n operations you should consider each operation type cost - O(1), O(log n), O(n), etc.
The second step will be to calculate the cost expectation according to the probability of each operation.

Regards,
Zachm

[humor_me]

I agree with your analysis. To give some background on the question, this is related to amortized cost analysis. There is a data structure where a operation takes constant time for the most part except when the data structure needs resizing in which case it needs time linear in the size of the structure.

But after performing the amortized cost analysis , we come to the conclusion that when we start with an empty data structure, the total cost of a series of n operations is O(n) even in the worst case and the amortized cost of each operation is O(1). So my guess is the question about "cost of a total of n operations on average" is really to slightly confuse the reader into thinking that the cost of a total of n operations is somehow in between O(n) and O(n^2) which isn't the case.

HM