10.1k views

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

MultiDequeue(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?

1. $Θ(n)$
2. $Θ(n + k)$
3. $Θ(nk)$
4. $Θ(n^2)$
in DS
edited | 10.1k views
+11
We can also say that we have [ Enqueue,Enqueue.........(n-1) times,MultiDequeue ] total n operation.First n-1 enqueue operation takes n-1 steps and last MultiDequeue (with m = n-1) will take n-1 steps. So total 2n -2 ops are performed in worst case O(n).
+1

what if the following operation is performed

1 Enqueue and 1 Dequeue--------2

2 Enqueue and 2 Dequeue--------4

3 Enqueue and 3 Dequeue--------6

.

.

(n-1)  Enqueue and (n-1) Dequeue---------(n-1)*2

​​​​​​​ n Enqueue and n Dequeue-------------n*2

so total will be = 2+4+6+8........2*(n-1) + 2*n

=2(1+2+3.......(n-1)+n) $= n^{2}+n$

$\approx \Theta (n^{2})$

+1
which concept is used here someone pls explain the code part
0

EDIT : missed the "worst case"

Best case will be sigma(k) right?

+3
in best case also we have to consider 'n' queue operations ..even if we consider n/2 enqueue and n/2 dequeue then also we get theta(n)..so it will be theta(n) only

And theta(n) itself says TC = O(n) and TC = sigma(n)

There are three possible operations on queue- Enqueue, Dequeue and MultiDequeue. MultiDequeue is calling Dequeue multiple times based on a global variable $k$. 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 $n$ only.

Correct Answer: $A$
by
edited
+5
The while loop will be continued until either k=0 or queue is empty....

hence while loop is limited in min( n,k)

It shud be thata(n+k)  (B)
+33
min ( n, k) is correct. But how it becomes theta(n + k)? Since the question asks for worst case, here k = n gives the worst case- loop cannot go beyond n times.
+3
Theta( N + K) does nt it mean the min of N and K?
+22
No. It means max not min.
+1
Splendid thinking !!!
+1
Suppose I perform n-1 Enqueue operations and 1 multidequeue operation where k<n. Then won't the complexity beO((n-1)+k) = O(n+k)??
+26
As you said if there are are n-1 Enqueue operations, the complexity will be O(n) for Enqueue only. At worst k can be anything but the loop in multidequeue can never execute more than (n-1) times as the loop is not only depending on k but also checking if Q is empty. So if Multidequeue is performed it will again take O(n). So overall complexity = O(n+k) =O(n+n) = O(n).

Hope it helps.
0
As you also wrote.. " So overall complexity = O(n+k) =O(n+n) = O(n)".. so the more specific one is O(n+k). Isn't it?
+6
By writing O(n+k)= O(n+n).

I simply mean that at worst case k can be n itself. k is not defined in terms of input. And we are talking about asymptotic notations not about the exact value.

So that can be written as O(n) only.
+1
Sir we are asked the worst case. Let take in consideration the case like. I will perform 8 operation in total.

1- enqueue 7 element and call 1 multidequeue (k =7) them total operation = 8 but the number of steps involved are 14 steps.  =  N + K

2- If we don't use multidequeue. We can only do n steps in n operations. ONly N steps we can take like If again n = 8 . ( n operations) then either enqueue or dequeue which will make it. n steps only.

So why worst casenis not N+K. here Theta is used so we should say exactly and it will be N +K exactly . will be O(N) eventually but not theta. ??
0
If multidequeue does k deque no. of operations is k + 1, not 1.
0

@ arjun sir

theta(n+k)=theta(n). Is that the only reason for choosing =theta(n) as the answer???

0
Here it is  mentioned that the queue is initially empty

What if the queue is full and multiqueue is called, it would still be theta(n) ?
0
I doubt it , if the queue is full and multi-dequeue is called , then it should take $\Theta (1)$ time.
+13

@Arjun Sir-In support of your claim: $\theta(n+k)=max(n,k)$ Above is a good try, an exercise from cormen.

0
@Shauya how O(1) time?? I think it will still be .O(n)!!

@aysuh I don't understand how coreman problem is supporting this answer??
0
are we assuming here that k>>n
0
each operation can be performed n times only since it is mentioned in question "worst case time complexity for n queue operations"

Since all operations need to be applied to an empty queue. There is no way multi-queue operation can execute fully, doesn't matter how big 'k' value is supplied, it will only execute in constant  O(1) time on 1 call(its while loop will not be executed). We can call Multi-Dequeue n times and tc will remain n*O(1)

Another operation that can be applied on an empty queue is Enqueue . Enqueue can be called n times.  .Therefore TC = O(n)

Dequeue can also be called on an empty queue. Each time it will take constant time. For n dequeue operations time taken will be n*O(1).

Therefore TC = theta(n).It is theta(n), because in this question for n queue operations, both best and the worst case will be O(n). Therefore it is average case also
0

@ arjun sir

theta(n+k)=theta(n). Is that the only reason for choosing =theta(n) as the answer???

@sushmita No. Time complexity : number of steps taken by algorithm.

When will the above snippet take maximum steps ? when our k = m

Worst case time complexity is asked. At max how many times our while loop will be executed? n times (when k will be n)

Hence Theta (n)

0

@Ayush Upadhyaya for your problem i think putting the constants c1 = 1 and c2 = 1/2 will work

0

Initially the queue is empty and we have to perform n operations. i) One option is to perform all Enqueue operation s i.e. n Enqueue operations. Complexity will beθ(n) or ii) We can perform a mix of Enqueue and Dequeue operations. It can be Enqueue for first n/2 times and then Dequeue for next n/2, or Enqueue and Dequeue alternately, or any permutation of Enqueues and Dequeues totaling ‘n’ times. Complexity will be θ(n) or iii) We can perform Enqueues and MultiDequeues. A general pattern could be as follows: Enqueue Enqueue ... (ktimes) MultiDequeue Enqueue Enqueue ... (ktimes) MultiDequeue ... Up to total n ---- k items enqueued -----k items deleted----k i tems enqueued ----k items deleted -- and so on. The number of times this k-Enqueues, MutiDequeue cycle is performed So, Complexity will be k times Enqueue + 1 MultiD equeue) =n or iv) We can just perform n MultiDequeues (or n Dequeues for that matter): Each time the while condition is false (empty que ue), condition is checked just once for each of the ‘n’ operations. So θ(n).
0
Can u plz tell that for enqueueing why are we performing DEQUEUE operations .

Also how come in multidequeue u r doing enqueue operations ? when we have only DEQUEUE there ?
0
the example explains the situation where random enqueue and dequeue are called. DEQUEUE is not called for enqueue and vice-versa, they are separately called, and then the example calculates the complexity for that situation.
0
I find the exact same words in Gateforum study material  :P
the answer will be A , i.e theta(n)

explanation : if you read the question closely , they have said that Queue is initially empty . So , when the line "While(Q is not empty)" is checked it turns out to be false and nothing is done by " Multi-Dequeue(Q) " , hence constant time or theta(1) . According to the question , this operation is performed for n times , thus n * theta(1) = theta(n)

hope i was clear enough
0
Very important point, if we want to know the complexity without assuming we are doing some en-queue operations. (Y)
0
Thats a Superb Explanation !!!!  :)
+1
your judgment of question is completely wrong. n queue means either of enqueue, dequeue, multidequeue.
+2

Wrong judgement

Queue is initially empty and we have to perform n queue operations (i.e Enqueue, Dequeue, Multidequeue), then we have to take the worst case among all the operations.

0

What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue? (GATE CS 2013)

+1

@Nandkishor3939 Have you seen GATE-2013-44 question in official question paper? Kindly do that.