Having the following operation that should be implemented using sorted linked list:
Insert(x): insert element x to the data structure and delete all keys smaller than x. (x is a real number)
the operation goes through the list and deletes elements until it gets to an element greater than the inserted x.
Complexity requirement of the operation is: O(1) amortized.
My prof. has published the solution explanation as follows but I am not convinced yet of its amortized complexity:
"Insert might take O(n) worst-case but O(1) amortized" , explaining: "Whenever we pass through an element it gets deleted thus we "touch" every element twice (when inserted and when deleted)"
My question is the complexity O(1) amortized? (assuming he used the accounting method for explaining his analysis, no need for potential function I just would like to understand why is it O(1) amortized).
Let's assume we always insert numbers smaller than all numbers in the linked list. it turns insert(x) the regular insertion that we know from linked lists. I don't understand why should it work O(1) amortized. I would love to get a detailed explanation! (my prof. is not accepting questions at the moment) your help is greatly appreciated.
Edit: I have just noticed that my claim above is not valid. If we were to insert elements smaller than all elements, this takes O(1) worst-case, because its place is on the beginning of the list (since it’s sorted). But still can’t get the amortized analysis.
After the edit, since I noticed the case an element smaller than all elements is placed on the beginning of the list, I understand now why it works. using the accounting method, we "pay" for the deletion of every element when inserting it. I think it should work to define the potential function to be the number of elements in the list, since after inserting an element it can either be reduced by the number of elements smaller than the element inserted, or increased by 1 (the case I mentioned above which takes O(1) worst-case, thus O(1) amortized implementing the potential function I suggested).