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?
1
Θ(n)
2
Θ(n + k)
3
Θ(nk)
4
Θ(n2)