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

We can also say that we have [ Enqueue,Enqueue.........(n-1) times,MultiDequeue ] total n operation.First n-1 enqueue operation takes n-1 steps and last MultiDequeue (with m = n-1) will take n-1 steps. So total 2n -2 ops are performed in worst case O(n).

---

what if the following operation is performed 

 1 Enqueue and 1 Dequeue--------2

 2 Enqueue and 2 Dequeue--------4

 3 Enqueue and 3 Dequeue--------6

.

.

(n-1)  Enqueue and (n-1) Dequeue---------(n-1)*2

​​​​​​​ n Enqueue and n Dequeue-------------n*2

so total will be = 2+4+6+8........2*(n-1) + 2*n

=2(1+2+3.......(n-1)+n)       

$= n^{2}+n$

$\approx \Theta (n^{2})$

---

which concept is used here someone pls explain the code part

---

@Ayush Upadhyaya had it been best case, then theta (k) ?

EDIT : missed the "worst case"

Best case will be sigma(k) right?

@jatin khachane 1 ?

---

in best case also we have to consider 'n' queue operations ..even if we consider n/2 enqueue and n/2 dequeue then also we get theta(n)..so it will be theta(n) only

And theta(n) itself says TC = O(n) and TC = sigma(n)

---

This is an apti question, EQ = O(1), DQ = O(1) , MultiDQ = O(k) ; but you gotta notice here, if you wanna pop “k” elements, and decide not to use MultiDQ but do via DQ only, you will still have k.O(1) = O(k) only. Overall what I wanna say is, DQ and MultiDQ is one and same. So on an avg, for a element every operation takes O(1) only. Now, if there you are running “n” operations, that means you should have some numbre of EQ operations, say “x”. then you may have “n-x” number of DQ opeartions, so overall your complexity becomes : O(x+n-x) = O(n) only.  This is very intuitive, don’t read the rest of the comments, it will only confuse you, try applying intuitional understanding to this.

---

What is the worst case time complexity of a sequence of $n$ MultiDequeue operations on an initially empty queue?

Is it $\Theta (nk)$?

---

you didn’t understand the question the questions puts a limit i.e. just use $n$ queue operations

you used 2+4+8...=n(n+1) operations

in worst case we should use $n$ queue operations

no matter what you do you can’t exceed time complexity O(n)

---

@pankaj pal

They have asked to perform n operation in total, you are performing $n^2$ operation.

---

@Proton it's a pretty bold assumption that k = n-1. Especially when you've been given O(n+k) as a possible option. 

So by your approach, if k << n-1, the answer is very easily O(n+k) which, in fact, is more generic. 

---

@thewolf No. They are not the same. 

Using a single MultiDQ operation will give you a complexity of O(k). On the other hand, it'll take you 'k' DQ operations to get a complexity of O(k).

Even though the resulting complexity is same, it's doesn't seem like a correct approach since MultiDQ and DQ need different number of operations to get O(k) - which is important because we're only given a limited number of operations. 

---

@Sachin Mittal 1 sir, this was the question I was asking, we come up with the conclusion that, K can be anything as it is defined global, so if we take like K = 2^n even though our function still be running in O(n) time as while the queue is empty condition is there, and if we say O(n+k) then it will be 2^n which is definitely the wrong as maximum n operations are done. So I believe that’s the reason O(N) is the answer.

@jiren 

---

@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

There are three possible operations on queue- Enqueue, Dequeue and MultiDequeue. MultiDequeue is calling Dequeue multiple times based on a global variable $k$. Since, the queue is initially empty, whatever be the order of these operations, there cannot be more number of Dequeue operations than Enqueue operations. Hence, the total number operations will be $n$ only.

Correct Answer: $A$

Comments

Hy suppose everyone has same doubt as i did. B) O(n+k)

By intuition and visual imagination seems right.

But actually A) O(n) is logically right,

Here is my logical reasoning behind. at any point of time k is static 0<=k<=n (At max k = n)

if in worst case k = n;

O(n+k) = O(n + n) = O(2n) = O(n) || as by amortized analysis 2n == 3n == 4n ==5n is equal etc

Correct me if i am flawed.

---

@kritikasingh Yes, in that case the worst case time complexity would have been O(n+k) because initially there are k elements, now we Enqueue n-1 elements whose time complexity is O(n-1) = O(n). Now there are total k+n-1 elements at this moment, and now we perform 1 Multidequeue operation ,so now even if k>>n then also the loop will run k times (which was not the case in the actual question) and hence time complexity for Multidequeue operation is O(k). Hence, total time complexity in worst case would have been O(n+k).

Correct me if I am wrong.

---

@reboot O(2n-2) and O(n) is the same.

Answer 2

Initially the queue is empty and we have to perform n operations. i) One option is to perform all Enqueue operation s i.e. n Enqueue operations. Complexity will beθ(n) or ii) We can perform a mix of Enqueue and Dequeue operations. It can be Enqueue for first n/2 times and then Dequeue for next n/2, or Enqueue and Dequeue alternately, or any permutation of Enqueues and Dequeues totaling ‘n’ times. Complexity will be θ(n) or iii) We can perform Enqueues and MultiDequeues. A general pattern could be as follows: Enqueue Enqueue ... (ktimes) MultiDequeue Enqueue Enqueue ... (ktimes) MultiDequeue ... Up to total n ---- k items enqueued -----k items deleted----k i tems enqueued ----k items deleted -- and so on. The number of times this k-Enqueues, MutiDequeue cycle is performed So, Complexity will be k times Enqueue + 1 MultiD equeue) =n or iv) We can just perform n MultiDequeues (or n Dequeues for that matter): Each time the while condition is false (empty que ue), condition is checked just once for each of the ‘n’ operations. So θ(n).

Comments

Can u plz tell that for enqueueing why are we performing DEQUEUE operations .

Also how come in multidequeue u r doing enqueue operations ? when we have only DEQUEUE there ?

---

the example explains the situation where random enqueue and dequeue are called. DEQUEUE is not called for enqueue and vice-versa, they are separately called, and then the example calculates the complexity for that situation.

---

I find the exact same words in Gateforum study material  :P

Answer 3

the answer will be A , i.e theta(n)

explanation : if you read the question closely , they have said that Queue is initially empty . So , when the line "While(Q is not empty)" is checked it turns out to be false and nothing is done by " Multi-Dequeue(Q) " , hence constant time or theta(1) . According to the question , this operation is performed for n times , thus n * theta(1) = theta(n)

hope i was clear enough

Comments

Wrong judgement @Abir Mazumder 

Queue is initially empty and we have to perform n queue operations (i.e Enqueue, Dequeue, Multidequeue), then we have to take the worst case among all the operations.

---

Actual queston asked in gate

What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue? (GATE CS 2013)

He answered according to this

---

@Nandkishor3939 Have you seen GATE-2013-44 question in official question paper? Kindly do that.

 

Answer 4

initially queue is empty and hence while loop will never going to be executed and therefore time complexity is not going to be depend on k, and thus it will be only O(n).

Comments

Here the multideque operation is depends upon the number of elements present in the queue and the the value of k...and worst case happens when value of k is equal to the number of elements present in that queue...