Arjun Suresh (talk | contribs) (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 ...") |
Arjun Suresh (talk | contribs) |
||
| (13 intermediate revisions by the same user not shown) | |||
| 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. | ||
| − | < | + | <syntaxhighlight lang="c"> |
MultiDequeue(Q){ | MultiDequeue(Q){ | ||
m = k | m = k | ||
| Line 8: | Line 8: | ||
} | } | ||
} | } | ||
| − | </ | + | </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? | ||
| 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}} | ||
| − | |||
| − | |||
| − | |||
| − | |||
| + | [[Category: GATE2013]] | ||
| − | + | [[Category:Algorithms & Data Structures Questions from GATE]] | |
| − | |||
| − | |||
| − | |||
| − | [[Category: | ||
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)$
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.
Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.
GATECSE <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)$