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.

  • 2
    $\begingroup$ "Here is my exercise, how do I solve it? I don't know how to start" questions often aren't very useful to others. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    Sep 29, 2020 at 1:28
  • $\begingroup$ If the problem statement is from published material, please properly attribute it. $\endgroup$
    – greybeard
    Sep 29, 2020 at 6:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.