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 full queue having n elements.?
(A) $\Theta(n) $
(B) $\Theta(n+k)$
(C) $\Theta(nk)$
(D) $\Theta(n^2)$
Here suppose we do one dequeue operation, then the loop will run for min(n,k) times. Now remaining 1 operation can be 1 enqueue operation which will take O(1) time so total complexity in this case will be O(min(n,k)).
Suppose we have k=1 and do (n-1) dequeue operations then it will take k*(n-1) time for multideqeue function and remaining one enqueue operation will take O(1) time . So in total we are getting O(kn) time in this case.
I am confused on how to handle 'k' parameter when we are calculating complexity.
NOTE :- n queue operations can be any combination of enqueue/dequeue/multi-dequeue(as defined) operation.
Any help would be appreciated.