Create a potential function for an abstract queue data structure to show constant amortized-time complexity

Question

Consider a variation of a Queue called MaxQueue, Q, that has the following operations:

dequeue(Q): removes and returns the first element of Q

enqueue(Q, s): Appends the integer s to the end of Q

maximum(Q): returns the largest integer in Q (but does not delete it)

The MaxQueue data structure also contains a sequence called the "suffix maxima". An element, x, is a "suffix maximum" in a sequence if all elements that occur after x are smaller in value.

MaxQueue is implemented using a singly linked list to represent the sequence with additional pointers to the front and back of the queue, and to have doubly linked list of the suffix maxima (which are arranged in the same order as they are in the sequence).

See this link for an example: https://ibb.co/f2KBtHN

---

Question: Prove that the amortized time complexity of the three operations are all O(1). (Define a potential function based on the number of suffix maxima in the sequence.

---

I don't really know how to start this question. I know a potential function tends to be of the form an + bm where a and b are constants and n and m are variables you set depending on the question. The hint suggests basing it off of the number of suffix maxima in the sequence which I believe should be reflected in these variables but I'm not sure how.

Answer 1

A potential function is a function computed from the state of the data structure that starts off bounded and never goes negative.

For any such function, for every operation, amortized_cost = O(real_cost + K*change_in_potential) for any constant K

That works because, since the potential function can't go negative, the bound on its initial value limits how negative the sum of all the changes in potential can be. Eventually, over many operations, the real cost will dominate.

So, if you want to prove O(1) bounds for all operations, your potential function has to:

1. increase by at most a constant amount during operations of constant cost; and
2. decrease by Ω(c) during any operation with cost c > O(1).

So look at your operations, and find some function of the state that can't be negative, decreases for every unit of work you do over and above constant time, and otherwise increases only by constant amounts in each operation.

I think you'll find that every unit of "extra work" you do decreases the length of the suffix maxima sequence, and it can only grow by one item per operation. The length of the suffix maxima sequence is therefore a viable potential function.