amortized bound of sorted linked list

Question

I am trying to prove that the amortized complexity of insert operation in a sorted LinkedList is O(1). I know that the worst case time is O(n) but finding it hard to find an appropriate potential function. I'll be glad if someone could help.

Thanks.

Answer 1

O(1) amortized means that a sequence of n insertions costs O(n) time in the worst case. This is not true for this case because inserting the elements in reverse order takes O(n*n).