Question

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 (Enqueue, Dequeue and/or MultiDequeue) on an initially empty queue?

Accepted Answer

The correct answer is (A) Θ(n). Each MultiDequeue call does at most k basic Dequeue steps, so a single call could naively look like O(k), suggesting O(nk) for n calls — but that overcounts: across the ENTIRE sequence of n operations, the total number of elements ever dequeued (via ordinary Dequeue or via MultiDequeue's internal loop) can never exceed the total number of elements ever enqueued, which is at most n. So the aggregate cost of all dequeue-style work across the whole sequence is O(n), and each Enqueue itself is O(1), giving an overall Θ(n) for the whole sequence — this is a classic amortized/aggregate-analysis argument, not a per-call worst case multiplied naively by n.

Explanation