[Algorithms Design and Analysis]

A standard (FIFO) queue maintains a sequence of items subject to the following operations.

ENQUEUE(Q, x): Add item x to the end of queue Q. DEQUEUE(Q): Remove and return the item at the beginning of queue Q; return NULL if Q is empty. SIZE(Q): Return the number of items currently stored in queue Q.

It is easy to implement a queue using a doubly-linked list, so that it uses O(n) space (where n is the number of items in the queue) and the worst-case time for each of these operations is O(1).

Consider the following new operation, which removes every tenth element from the queue, starting at the beginning, in O(n) worst-case time.

Prove that, for any sequence of m operations (where each operation the sequence is either ENQUEUE, DEQUEUE, or DECIMATE), the total running time for the sequence is O(m).

Note: 1. You may assume that there is unlimited amount of memory available to store a queue. 2. (Cost model) Each enqueue or dequeue operation costs 1 credit.

1: DECIMATE (Q) n SIZE Q) for i 0 to n -1. if (i mod 10 0) DE QUEUE (Q) else ENQUEUE (Q,DEQUEUE(Q)) 8