MyQuestionIcon

1

You visited us 1 times! Enjoying our articles? Unlock Full Access!

Property 1

Consider the ...

Question

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

Multi - Dequeue (Q)
{
m = k ;
while ((Q is not empty) and (m > 0))
{
Dequeue (Q);
m = m - 1 ;
}
}

What is the worst case time complexity of a sequence of n queue operations on an initially empty queue?

A

Θ (n)

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

B

Θ (n + k)

No worries! We‘ve got your back. Try BYJU‘S free classes today!

C

Θ (n^{2})

No worries! We‘ve got your back. Try BYJU‘S free classes today!

D

Θ (n k)

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Open in App

Solution

The correct option is A $Θ (n)$
Since there are 3 queue operation i.e., enqueue, dequeue and Multi - dequeue.

'n' enqueue operation will take $Θ (n)$ time, 'n' dequeue operation will $Θ (n)$ time, 'n' Multi- dequeue operation will take $Θ (n)$ time i.e., Min (n, k) but for worst case when n = k time complexity will be $Θ (n)$

Suggest Corrections

thumbs-up

2

Similar questions

Q. Suppose a circular queue of capacity (n - 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array indeed variables respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are

Q. Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are:

(i) is Empty (Q) : returns true if the queue is Empty, false otherwise.
(ii) delete (Q) : delete the elements at the front of the queue and returns its value.
(iii) insert (Q, i) : insert the integer i at the rear of the queue.

Consider the following functions:

void f (queue Q)
{
int i;
if (! is Empty (Q))
{
i = delete (Q);
f(Q);
insert (Q, i);
}
}

What operation is performed by the above function f?

Q. A queue is implemented using an array such that n ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?

Q. A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time?

Q. An implementation of queue Q, using two stacks S1 and S2, is given below:

void insert(Q, x)
{
push(S1, x);
}
void delete (Q, x)
{
if (stack -empty (S2)) then
if ( stack - empty(S1)) then
{
print ("Q is empty");
return;
}
else while (! stack - empty(S1))
{
x = pop (S1);
push(S2, x);
}
x = pop(S2);
}

Let n insert and

(m \leq n)

delete operations be performed in an arbitary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the processes. Which one of the following is true for all m and n?

View More

Join BYJU'S Learning Program

similar_icon

Related Videos

lock

Property 1

MATHEMATICS

Watch in App

explore_more_icon

Explore more

Standard XII Mathematics

Join BYJU'S Learning Program

CrossIcon