(12 intermediate revisions by the same user not shown)
Line 21: Line 21:
  
  
 +
==={{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.
  
 +
{{Template:FBD}}
  
<div class="fb-like"  data-layout="standard" data-action="like" data-show-faces="true" data-share="true"></div>
 
 
 
<div class="fb-share-button"  data-type="button_count"></div>
 
  
 +
[[Category: GATE2013]]
  
 
+
[[Category:Algorithms & Data Structures Questions from GATE]]
<disqus/>
 
 
 
 
 
[[Category: GATE2013]]
 

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)$





blog comments powered by Disqus