Time complexity of dequeue function (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 &gt; 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.
It's $\Theta(n)$. Observe that if you are limited by $n$ operations, the total number of elements that ever enter the queue is less than or equal to $n$. Furthermore, every element is processed at most twice: once when it enters the queue, and once when it leaves the queue, therefore the total time is at most a constant times $n$.