19,485 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)$

9 Comments

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).

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})$

which concept is used here someone pls explain the code part
edited by

@Ayush Upadhyaya had it been best case, then theta (k) ?

EDIT : missed the "worst case"

Best case will be sigma(k) right?

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)
This is an apti question, EQ = O(1), DQ = O(1) , MultiDQ = O(k) ; but you gotta notice here, if you wanna pop “k” elements, and decide not to use MultiDQ but do via DQ only, you will still have k.O(1) = O(k) only. Overall what I wanna say is, DQ and MultiDQ is one and same. So on an avg, for a element every operation takes O(1) only. Now, if there you are running “n” operations, that means you should have some numbre of EQ operations, say “x”. then you may have “n-x” number of DQ opeartions, so overall your complexity becomes : O(x+n-x) = O(n) only.  This is very intuitive, don’t read the rest of the comments, it will only confuse you, try applying intuitional understanding to this.

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

Is it $\Theta (nk)$?

you didn’t understand the question the questions puts a limit i.e. just use $n$ queue operations

you used 2+4+8...=n(n+1) operations

in worst case we should use $n$ queue operations

no matter what you do you can’t exceed time complexity O(n)
@pankaj pal

They have asked to perform n operation in total, you are performing $n^2$ operation.

9 Answers

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 number of Dequeue operations than Enqueue operations. Hence, the total number operations will be $n$ only.

Correct Answer: $A$
by

24 Comments

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)
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.
Theta( N + K) does nt it mean the min of N and K?
No. It means max not min.
reshown
Splendid thinking !!!
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)??
edited
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.
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?
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.
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. ??
If multidequeue does k deque no. of operations is k + 1, not 1.

@ arjun sir

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

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) ?
I doubt it , if the queue is full and multi-dequeue is called , then it should take $\Theta (1)$ time.

@Arjun Sir-In support of your claim: $\theta(n+k)=max(n,k)$

Above is a good try, an exercise from cormen.

@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??
are we assuming here that k>>n
edited by
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

@ 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)

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

@Rajendra Dangwal your comment made everything crystal clear.

If the question has not mentioned that it is initially empty and instead it mentions that it has k elements already and then we enqueue     n elements and then multidequeue is called then what will be its complexity ?

Is it O(n+n+k) which is equivalent to O(n+k)?

the statement

Hence, the total number operations will be n only.

seems wrong to me. Because if we do n-1 ENQUEUE operations and then one multiDequeue with k>(n-1), then there will be 2n-2 operations.

Hy suppose everyone has same doubt as i did. B) O(n+k)

By intuition and visual imagination seems right.

But actually A) O(n) is logically right,

Here is my logical reasoning behind. at any point of time k is static 0<=k<=n (At max k = n)

if in worst case k = n;

O(n+k) = O(n + n) = O(2n) = O(n) || as by amortized analysis 2n == 3n == 4n ==5n is equal etc

Correct me if i am flawed.
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).
by

3 Comments

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 ?
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.
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

6 Comments

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

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.

Actual queston asked in gate

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

He answered according to this

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

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).
by

1 comment

Here the multideque operation is depends upon the number of elements present in the queue and the the value of k...and worst case happens when value of k is equal to the number of elements present in that queue...
First of all n Queue operation means any order of enqueue, dequeue, or multidequeue. Now the question asks for worst case scenario which is possible when we do (n-1) enqueue and 1 multidequeue operation in this order. and moreover answers are given in Θ notation means tightest upper bound for worst case. now in worst case we can write complexity as O(n + k) but value of k can never going beyond n so we can say tightest upper bound is Θ (n + n) = Θ (n)

Disclaimer: This is not my answer but I found this answer really helpful and elaborate.

by
Ans ->A

In best case it would be Θ(n[for some enqueue (n-k) ]+k[some dequeue operations (k) ]) because you would not be deleting all the elements in that case ,and in worst case you have to delete all the elements ,considering the fact that you cant do more then n dequeue operations and hence answer would be Θ (2n)~ Θ(n), to perform this you can do n-1 enqueue operations and then 1 multidequeue operations where k=n-1.

If we see the question its mentioned in initially empty queue and in the code the if condition is false so we don’t enter the loop. Thus for “n” queue operations just the for loop condition is checked “n” times. Thus option A is correct

by
worst case scenario for program execution  –

n-1 enqueue operations and 1 mulitdequee operation with k>=n-1

which takes O(n-1)+O(n-1)=O(n)

option a – is true

option b and c can be eliminated,

assume k =O(n^2)

the time complexity  will be O(n) for any permutation of queue opeartions even if k=O(n^2)
Answer:

4 answers
1
7 answers
2
7,540 views
2 answers
3
7,767 views
6 answers
4