GATE CSE 2013 | Question: 44

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?

• A. $Θ(n)$
• B. $Θ(n + k)$
• C. $Θ(nk)$
• D. $Θ(n^2)$

Comments

@Nikzszz actually it can’t be greater than O(n) because even if $K=2^n$ , still the while loop will run for max $n-1$ times (if we consider the worst case where all $n-1$ were $Enqueue$ operations of $O(1)$ each) and last operation was $MultiQueue(Q)$.

---

yeah actually we had a discussion in private channel, for what reason theta(n+k) is not a valid answer, and we come up with this conclusion that the way program is written it won’t cross O(n) no matter what value of k is it big or small. So to counter O(n+k) we come up with this, as if we put K = 2^n, Theta(n+k) will give us  2^n, but it’s not a valid answer. So that’s why theta(n+k) is not an answer to this question even if it was an MSQ question. The problem arises, because as given k is global, I thought it to be global constant, but it can be a function of the form 2^n too. So got my mistake later. Thanks @Abhrajyoti00 for replying.

---

Suppose at first we perform k enqueue operations i.e., calling enqueue() k times. So it takes θ(k). Now remaining queue operations are n-k. Now we call mutidequeue one time which dequeue all k elements from queue and takes another θ(k). So total θ(k)+θ(k) and the remaining queue operations are n-k-1.

Now again we repeat the above procedure. Total time would become θ(k)+θ(k)+θ(k)+θ(k) and remaining queue operations are n-k-1-k-1.

If we notice carefully then for each term after n we are getting a time complexity of θ(k). So if we count no of k-1 terms and then multiply by 2 then we get how many times we are adding θ(k). Let that count be x.

So at the end n-x(k+1)=0

or x=n/(k+1) which is approx n/k.

So total no of terms after n in the series n-k-1-k-1….. are 2n/k (because no of times k+1 occur is n/k)

So we are adding θ(k)  2n/k times.

So worst case time complexity is θ( k * (2n/k) ) which is θ(2n) or θ(n).

This can be proved intuitively. For each element we can perform one enqueue and one dequeue at max or n-1 enqueue in one go and then calling multidequeue() to dequeue all n-1 elements. So time complexity would be θ(2(n-1)) or θ(2n) or θ(n)

Answer 1

First of all n Queue operation means any order of enqueue, dequeue, or multidequeue. Now the question asks for worst case scenario which is possible when we do (n-1) enqueue and 1 multidequeue operation in this order. and moreover answers are given in Θ notation means tightest upper bound for worst case. now in worst case we can write complexity as O(n + k) but value of k can never going beyond n so we can say tightest upper bound is Θ (n + n) = Θ (n)

Answer 2

Disclaimer: This is not my answer but I found this answer really helpful and elaborate.

Source: http://docshare02.docshare.tips/files/24085/240859254.pdf

Answer 3

Ans ->A

In best case it would be Θ(n[for some enqueue (n-k) ]+k[some dequeue operations (k) ]) because you would not be deleting all the elements in that case ,and in worst case you have to delete all the elements ,considering the fact that you cant do more then n dequeue operations and hence answer would be Θ (2n)~ Θ(n), to perform this you can do n-1 enqueue operations and then 1 multidequeue operations where k=n-1.

Answer 4

If we see the question its mentioned in initially empty queue and in the code the if condition is false so we don’t enter the loop. Thus for “n” queue operations just the for loop condition is checked “n” times. Thus option A is correct