Queue

Question

Consider the following operation along wit he queue and dequeue operation on queue,where k is global parameter

multidequeue(q)

{

m=k

while(q is not empty and m>o)

{

dequeue(q)

m=m-1

}}

worst time complexity of a sequence of n multidequeue() operations on initially empty queue

A)theta(n)

b)theta(n+k)

c)theta(n^2)

d)theta(nk)

Answer 1

Since initially Q is empty while loop wil never execute Ok.Now since operation multideque is performed n times.so overall time complexity would be theta(n).

Comments

what if the queue is full,then what will be the answer?

---

I think answer would be theta(n+k) try to run the algo using k=4 and assume queue have 4 elements,loop will run 4 time that means theta(k) and multidequeue operation is called theta(n) time so theta(n+k) oveall.

---

lets assume multidequeue is called n times(n=5)

k=4

now 4 times on multiqueue operation is called,k becomes zero now and n becomes 5-1=4

so now one more time multidequeue called to complete the n times calling

so the loop has executed only 5 times which is n

therefore should be theta(n) right?

am not sure if i make sense

do correct me if am wrong

Answer 2

Since initially queue is empty and while loop will not execute and since the function calling n times with constant time 1 answer should be theta(nk)

Comments

for initially empty queue the answer is theta(n)