# 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 > 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.

• @Dukeling You can assume it n. I will include it in the question. – Zephyr Dec 24 '17 at 12:29

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$.
• Also why is $\Theta(n+k)$ not the correct answer? – Zephyr Dec 24 '17 at 5:37
• The $k$ parameter is irrelevant to the complexity. Also, $\Theta(3n-4) = \Theta(n)$, I suggest you review the Landau notation. – quicksort Dec 24 '17 at 8:42
• I know that constants are irrelevant in landau notation. Wouldn't $\Theta(n+k)$ be more precise ? – Zephyr Dec 24 '17 at 8:45
• No. $k$ is irrelevant. – quicksort Dec 24 '17 at 8:46