Question

How many enqueue and dequeue operations are required to access n/2th element of queue of n elements?

Answer 1

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 full  queue having n elements.?  

(A) Θ(n)Θ(n) 

(B) Θ(n+k)Θ(n+k)

(C) Θ(nk)Θ(nk)

(D) Θ(n2)Θ(n2)

Here suppose we do one dequeue operation, then the loop will run for min(n,k) times. Now remaining 1 operation can be 1 enqueue operation which will take O(1) time so total complexity in this case will be O(min(n,k)).

Suppose we have k=1 and do (n-1) dequeue operations then it will take k*(n-1) time for multideqeue function and remaining one enqueue operation will take O(1) time . So in total we are getting O(kn) time in this case.

I am confused on how to handle 'k' parameter when we are calculating complexity.

NOTE :- n queue operations can be any combination of enqueue/dequeue/multi-dequeue(as defined) operation.