# general question amortized cost and worst case

lets say a data structure has operations called insert and delete both of which take O(log(n)) worst case. Suppose the amortized cost of insert is O(log(n)) and the amortized cost of delete is O(1).

Now if a sequence that has n delete operations performed on this data structure that has n elements currently, then what is the worst case? If delete takes O(1) amortized cost does this mean the worst case (not amortized) is O(n) for n delete's ?

I think no because it doesn't seem right but I'm not sure how to explain it

• Amortization usually refers to the entire sequence of operations on a data structure, not just some of them. – Yuval Filmus Mar 23 at 8:12
• I think you are right. Amortized cost is measured over unspecified-long sequence of operations, but since you can't delete more than N elements from this sequence, average cost of each operation in this procedure should be O(1) and therefore entire procedure is O(N). In other words, if this procedure require more than O(N) time, how one can say that amortized deletion operation cost is O(1)? – Bulat Mar 23 at 8:53
• sorry, I mean that answer to the question is yes, and therefore you are wrong – Bulat Mar 23 at 9:05

Consider a data structure supporting operations $$O_1,\ldots,O_m$$. These operations have amortized cost $$T_i$$ (where $$T_i$$ could depend on parameters) if the total cost of a sequence of operations run immediately after initializing the data structure consisting of $$c_i$$ many operations of type $$O_i$$ is at most $$c_1 O_1 + \cdots + c_m O_m.$$ This bound only works if we consider all operations done on the data structure since initialization.
• @Bulat This is meaningless. Taking $n=1$, we recover worst case complexity. – Yuval Filmus Mar 24 at 6:10