Amortized Analysis On List

Question

We want to have a set of n linear list to doing following operation:

Insert(x,i) : insert new elemets x on list i, and cost of this operation is 1.

Sum(i) : calculate sum of all elements in list i and replace whole elements of list with the calculated sum, and cost is equal to number of elements in list i when we using this operation.

if we start with empty list and do the above operation in arbitrary manner, what is the amortized cost of each operation :

1)insert : 2, sum : 1
2)insert : 1, sum : 2
3)insert : 1, sum : n
4)insert : n, sum : 1

who can help me to understand how to solve this example and say why (2) is true?

Answer 1

I'm not quite familiar with amortized analysis, but I guess you could reason about it as follows (using the accounting method).

Say you charge an insert with $2\$$. Because you only need $1\$$ to perform the insert, you'll get for every inserted element in the list $1\$$ saving. This saving can be used when sum is being performed. For every element in the list, there is an extra $1\$$ left from the insertion and it can be used by sum to read the elements from the list, but then sum has $1\$$ left to calculate the sum and store the element.

This way I would say (1) is the right answer, rather than (2), because in (2) there is no way to pay for your sum with only a constant factor if you don't have anything left from your insertions.