(Created page with "Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter. <pre> <code class="language-c"> MultiDequeue(Q){ m = k ...")
 
Line 1: Line 1:
 
Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.  
 
Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.  
<pre> <code class="language-c">
+
<syntaxhighlight lang="c">
 
MultiDequeue(Q){  
 
MultiDequeue(Q){  
 
m = k  
 
m = k  
Line 8: Line 8:
 
}  
 
}  
 
}  
 
}  
</code></pre>
+
</syntaxhighlight>
 
What is the worst case time complexity of a sequence of $n$ queue operations on an initially empty  
 
What is the worst case time complexity of a sequence of $n$ queue operations on an initially empty  
 
queue?
 
queue?

Revision as of 11:12, 8 December 2013

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

Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.

 <code class="language-c">
MultiDequeue(Q){ 
	m = k 
	while (Q is not empty) and (m > 0) { 
		Dequeue(Q) 
		m = m – 1 
	} 
} 
</code>

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