(Solution)
 
(3 intermediate revisions by the same user not shown)
Line 21: Line 21:
  
  
===Solution===
+
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
 
  There are three possible operations on queue- Enqueue, Dequeue and MultiDequeue. MultiDequeue is calling Dequeue multiple times based on a global variable <math>k</math>. Since, the queue is initially empty, whatever be the order of these operations, there cannot be more no. of Dequeue operations than Enqueue operations. Hence, the total no. operations will be <math>n</math> only.
 
  There are three possible operations on queue- Enqueue, Dequeue and MultiDequeue. MultiDequeue is calling Dequeue multiple times based on a global variable <math>k</math>. Since, the queue is initially empty, whatever be the order of these operations, there cannot be more no. of Dequeue operations than Enqueue operations. Hence, the total no. operations will be <math>n</math> only.
  
Line 28: Line 28:
  
 
[[Category: GATE2013]]
 
[[Category: GATE2013]]
[[Category: Previous year GATE questions]]
+
 
[[Category:Algorithms & Data Structures]]
+
[[Category:Algorithms & Data Structures Questions from GATE]]

Latest revision as of 11:29, 15 July 2014

Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter. <syntaxhighlight lang="c"> MultiDequeue(Q){ m = k while (Q is not empty) and (m > 0) { Dequeue(Q) m = m – 1 } } </syntaxhighlight> 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)$


Solution by Arjun Suresh

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




blog comments powered by Disqus

Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter. <syntaxhighlight lang="c"> MultiDequeue(Q){ m = k while (Q is not empty) and (m > 0) { Dequeue(Q) m = m – 1 } } </syntaxhighlight> 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)$


Solution[edit]

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




blog comments powered by Disqus