GATE CS 2013 Q.44 (CS Q.44): Stacks and Queues

Consider the following operation along with Enqueue and Dequeue operations on queues, where $k$ is a global parameter.

MultiDequeue(Q){
    m = k
    while (Q is not empty) and (m > 0) {
        Dequeue(Q)
        m = m - 1
    }
}

What is the worst case time complexity of a sequence of $n$ queue operations on an initially empty queue?

$\Theta(n)$

$\Theta(n + k)$

$\Theta(nk)$

$\Theta(n^2)$

Official answer and solution

Official answer: A
From: Official GATE 2013 answer key

Solution

Use aggregate amortized analysis by tracking the lifecycle of each element enqueued in the queue.

Consider an arbitrary sequence of $n$ operations performed on an initially empty queue $Q$ .

The permissible operations are Enqueue, Dequeue, and MultiDequeue.
Since each Enqueue operation inserts exactly one element into $Q$ , at most $n$ elements can ever be enqueued across all $n$ operations.
An element can be removed by a Dequeue operation (whether called directly or called inside MultiDequeue) at most once.
Therefore, across the entire sequence of $n$ operations, the total number of times Dequeue(Q) can be executed is at most $n$ .
Each Enqueue takes $O(1)$ time. Outside the while-loop, each MultiDequeue takes $O(1)$ time to initialize $m$ . The while-loop iterations in MultiDequeue execute Dequeue(Q), each iteration accounting for the removal of one enqueued element.
Since at most $n$ removals can occur in total, the cumulative number of while-loop iterations over all operations in the sequence cannot exceed $n$ .

Thus, the total time for the entire sequence of $n$ operations is upper-bounded by $O(n)$ . Since each operation takes at least $\Omega(1)$ time, the sequence takes $\Omega(n)$ time. Therefore, the worst-case time complexity is $\Theta(n)$ , corresponding to option (A).

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2013 Computer Science and Information Technology (CS)
Question: 44 of 65, printed as CS Q.44
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source