Negative linear amortized time cost of operation obtained using the potential function method

Question

For a (linked) list of numbers there are 3 operations available.

Insert which operates in a constant time. Inserts a number at the beginning of the list.

Remove every second - time complexity is linear. Removes every second number from the list.

Remove every sixth - time complexity is linear. Removes every sixth number from the list.

Now I am supposed to find a potential function to show that amortized costs of all the mentioned operations are constant. If there were just the first two operations I would choose the potential function $\Phi(\text{list of length n}) =2n $. That's not enough for the third operation. Thus, I am basically forced to use the $\Phi(\text{list of length n}) =6n $ potential function.

Here I compute the amortized costs for all three operations with the mentioned potential function:

AC for Insert: $1 + 6(n + 1) - 6n = 7$

AC for Remove every second: $n + 6\lceil\frac{n}{2}\rceil - 6n = -2n + (n \mod 2)$

AC for Remove every sixth: $n + 6\lceil\frac{5n}{6}\rceil - 6n = (n \mod 6)$

Here I can finally explain my problem. As you can see for the second operation I get a negative linear complexity. Is that even allowed? Is that better than linear? How can I fix it if so?

Answer 1

It is allowed.

Whenever you insert a number, the potential method tells you to also remember that you might have to spend some time deleting it (given by the change in potential). The least efficient way to delete numbers is the second method, so you remember the amount of time it takes to use the second method to delete that number. This means that if you delete numbers via the first method, you're saving some time, which gives you a negative amortized runtime for that operation.

Effectively, whenever this happens, you can treat that operation as taking $0$ time: all of the time it might take has already been accounted for elsewhere in the analysis.

(That being said, if you're being really careful, you might assign actual coefficients to the runtimes of the three operations. In that case you could — depending on the values of those coefficients — discover that the third method is actually less efficient than the second method...)