(4 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>. But 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.
  
 
{{Template:FBD}}
 
{{Template:FBD}}
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>. But 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