The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+35 votes
5.6k 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)$
asked in DS by Boss (18.1k points)
edited by | 5.6k views
+3
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)       

\sum _{i{\mathop {=}}1}^{n}i={\frac {n(n+1)}{2}}

$= n^{2}+n$

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

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

4 Answers

+57 votes
Best answer
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.
answered by Veteran (355k points)
selected by
+2
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)
+12
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.
0
Theta( N + K) does nt it mean the min of N and K?
+8
No. It means max not min.
0
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)??
+4
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?
0
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.
+17 votes
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).
answered by (91 points)
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
+8 votes
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
answered by (99 points)
0
Very important point, if we want to know the complexity without assuming we are doing some en-queue operations. (Y)
+5 votes
initially queue is empty and hence while loop will never going to be executed and therefore time complexity is not going to be depend on k, and thus it will be only O(n).
answered by Active (2.7k points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,018 questions
45,509 answers
131,698 comments
48,742 users