GATE 2013

Question

Its GATE 2013 question

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?

What would be the worst case time complexity if n queue operations are performed on non-empty or full queue?? Due to this change will the answer remain same??

• A. Θ(n)
• B. Θ(n + k)
• C. Θ(nk)
• D. Θ(n²)

Answer 1

Firstly the time complexities of the functions are :

Enqueue : $O(1)$ , Dequeue : $O(1)$ and Multi-Dequeue : $O(k)$

Case 1 :

Now when it was empty then if we perform Enqueue and Dequeue n times (alternately) then our worst case complexity stands out to be $O(n)$.Further if we had performed the Multi-Dequeue operation on the empty queue then it would not implement the loop body due to being initially empty and on repeating the operation $n$ times we would get the complexity of $O(n)$.

Case 2 :

When the queue is full or non empty then if we do the  Enqueue and Dequeue n times (alternately) then time complexity would be $O(n)$.However if the no. of elements in the queue happen to be $n*k$ then by executing the Multi-Dequeue operation $n$ times we would get a time complexity of $O(n*k)$.Now if $k=n$ then our complexity would $O(n^2)$.So here the worst case complexity would be $max(O(n*k),O(n^2))$