Consider the following operation along with \(Enqueue \) and \(Dequeue \)…
2013
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?
- A.
\(Θ(n)\) - B.
\( Θ(n + k)\) - C.
\(Θ(nk) \) - D.
\(Θ(n^2) \)
Attempted by 343 students.
Show answer & explanation
Correct answer: A
Key idea: count the actual Dequeue actions across the sequence.
Each Enqueue or single Dequeue operation takes Θ(1) time.
A call to MultiDequeue performs up to k Dequeue operations, but every Dequeue (whether called directly or inside MultiDequeue) removes one element from the queue.
Since the queue starts empty, the total number of Dequeue actions over the entire sequence cannot exceed the number of Enqueue actions, which is at most n.
Therefore the total work for any sequence of n queue operations is Θ(n).
A video solution is available for this question — log in and enroll to watch it.